PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Mamnoon Siam
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Data-Structures.
PROBLEM:
There are N participants numbered from 1 to N, each having skill level 0. Also, there are M challenges numbered from 1 to M, each challenge is given by (L, R, X) implying for each player numbered from L to R inclusive if this player participates in this challenge, his skill level increases by X.
Now, there are Q compos, each compo specified by two integers A_i and B_i, including all challenges numbered from A_i to B_i. Each participant is allowed to select a subset of compos and participate in all challenges in selected compos (a challenge may participate in the same challenge more than once if included in different selected compos.
Find the maximum skill level each player can get by choosing compos optimally.
QUICK EXPLANATION
- Since there are M challenges, the value of a compo (the sum of skill gain of all active challenges) changes at most 2*M times, since only at 2*M positions either a challenge becomes active, or inactive.
- While changing the state of a challenge, we need to update the values of compos and take some of all positive values compos. The sum of values of all positive-valued compos is the maximum skill level current player can gain.
- In order to simulate the above efficiently, we can create N lists and in each list where either any challenge start or ends, we can add it to that position. Moving from left to right, we perform all changes in all lists up to list p to calculate skill level of player p
EXPLANATION
First of all, let us see how compos work and let’s denote the value of a compo to be the sum of skill gain of all challenges included in that compo, which are active.
Now, what is an active challenge? Suppose we are calculating the maximum skill level for player p. Then all challenges which affect the skill level of player p is an active challenge. By definition, each challenge (L, R, X) become active for all player L \leq p \leq R. Hence, if we consider players from 1 to N from left to right, each challenge shall become active only once, and then become inactive again only once.
Hence, there cannot be more than 2*M positions where the state of any challenge changes from active to inactive or vice versa. Now, whenever the state of a challenge changes, the value of all compos which contain this challenge is affected.
Now, since the constraints on Q and M are low, for each state change, we can manually update the value of each compo every time the state of any challenge changes.
Now, the problem is that we have a multi-set, initially empty, where some insertions and deletions take place and we need to answer the sum of positive elements present in the set. (For updating value of a compo, remove its old value and insert its new value). It is easy to see that keeping a sum variable is enough. Just increase it whenever a positive value is added, and reduce it when a positive value is removed.
This is sufficient to solve the problem, but can you solve a bonus variant?
Here, Each player is allowed to select at most C_i compos.
TIME COMPLEXITY
The time complexity is O(N + M*Q) per test case. Different implementations may have a log factor too.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,pair<int,int> > pp;
typedef long long ll;
#define N 100005
#define M 1005
#define Q 10005
int n,m,q;
pp queries[M];
pair<int,int> compos[Q];
vector<int> composIdx[M];
ll pref[N];
int main() {
// freopen("out.out", "w", stdout);
int t; scanf("%d", &t);
while(t--) {
scanf("%d%d%d", &n,&m,&q);
for(int i = 1; i <= m; i++) {
int x, y, z; scanf("%d%d%d", &x,&y,&z);
queries[i] = {x, {y, z}};
}
for(int i = 0; i < M; i++) composIdx[i].clear();
for(int i = 1; i <= q; i++) {
int x, y; scanf("%d%d", &x, &y);
compos[i] = {x, y};
composIdx[y].push_back(i);
}
for(int i = 0; i<= n; i++) pref[i] = 0;
multiset<pp> s;
for(int i = 1; i <= m; i++) {
s.insert({queries[i].first, {i, 0}});
s.insert({queries[i].second.first + 1, {i, 1}});
for(int compoIdx: composIdx[i]) {
ll sum = 0, last = 0;
for(auto p: s) {
int idx = p.second.first;
if (idx < compos[compoIdx].first || idx > compos[compoIdx].second) continue;
ll sign = (p.second.second == 0) ? 1 : -1;
if (sum > 0) {
pref[last] += sum, pref[p.first] -= sum;
}
sum += sign * queries[idx].second.second;
last = p.first;
}
}
}
for(int i = 1; i <= n; i++) {
pref[i] += pref[i - 1];
if (i != 1) printf(" ");
printf("%lld", pref[i]);
}
printf("\n");
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int l[1234],r[1234],x[1234];
int le[12345],re[12345];
int posi[123456],haha[1234][3123],ans[3123];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,m,q;
cin>>n>>m>>q;
int i;
vi vec;
vec.pb(0);
vec.pb(n);
f(i,1,m+1){
cin>>l[i]>>r[i]>>x[i];
l[i]--;
r[i]--;
vec.pb(l[i]);
vec.pb(r[i]+1);
}
sort(all(vec));
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
int j=0,k=0;
rep(i,n){
if(i==vec[k]){
posi[i]=j++;
k++;
}
else{
posi[i]=j-1;
}
}
int siz=j;
//cout<<siz<<endl;
f(i,1,m+1){
l[i]=posi[l[i]];
r[i]=posi[r[i]];
}
//cout<<<<l[m]<<" "<<r[m-1]<<endl;
rep(i,q){
cin>>le[i]>>re[i];
le[i]--;
}
rep(i,siz){
haha[0][i]=0;
}
f(i,1,m+1){
rep(j,siz){
haha[i][j]=haha[i-1][j];
}
f(j,l[i],r[i]+1){
haha[i][j]+=x[i];
}
}
rep(j,siz){
ans[j]=0;
}
//cout<<k<<endl;
rep(i,q){
rep(j,siz){
if(haha[re[i]][j]-haha[le[i]][j]>=0){
ans[j]+=haha[re[i]][j]-haha[le[i]][j];
}
}
}
rep(i,n){
if(i!=n-1)
cout<<ans[posi[i]]<<" ";
else
cout<<ans[posi[i]]<<endl;
}
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class CHADAY{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), m = ni(), q = ni();
long[] chV = new long[1+m];
Queue<Integer>[] Q = new ArrayDeque[1+n];
for(int i = 1; i<= n; i++)Q[i] = new ArrayDeque<>();
for(int i = 1; i<= m; i++){
int l = ni(), r = ni();
chV[i] = nl();
Q[l].add(i);
if(r+1 <= n)Q[r+1].add(-i);
}
int[][] compo = new int[q][];
for(int i = 0; i< q; i++)compo[i] = new int[]{ni(), ni()};
long[] cVal = new long[q];
long sum = 0;
for(int p = 1; p <= n; p++){
while(!Q[p].isEmpty()){
int x = Q[p].poll();
if(x > 0){
//Adding challenge
for(int i = 0; i< q; i++)
if(compo[i][0] <= x && x <= compo[i][1]){
if(cVal[i] > 0)sum -= cVal[i];
cVal[i] += chV[x];
if(cVal[i] > 0)sum += cVal[i];
}
}else{
x = -x;
//Removing challenge
for(int i = 0; i< q; i++)
if(compo[i][0] <= x && x <= compo[i][1]){
if(cVal[i] > 0)sum -= cVal[i];
cVal[i] -= chV[x];
if(cVal[i] > 0)sum += cVal[i];
}
}
}
p(sum+" ");
}
pn("");
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CHADAY().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 