oj.uz

Submission #805206

# Submission time Handle Problem Language Result Execution time Memory
805206 2023-08-03T14:01:31 Z moe_solution(#10139) Vera and Modern Art (CCO17_art) C++17
25 / 25
 2421 ms 67004 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=array<int,2>;
using ti4=array<int,4>;
using pll=array<ll,2>;
const int N=2e5+5,M=1e7+5;
ll pw[M];
int n,q,v[N];
ll a[N][2],b[N][2];
int c[N][2],d[N][2];
pii in[N],out[N],dfn[N]; int k[2];
ti4 ev[2*N];
int idx[N];
int ans[N];
struct Fen{
	int F[M]={0};
	void upd(int i,int v){
		for(;i<=k[1];i+=i&-i) F[i]+=v;
	}
	int qry(int i){
		int r=0;
		for(;i;i-=i&-i) r+=F[i];
		return r;
	}
}F;
void build(int bit,int c,vector<int> P,vector<int> Q){
	if(P.empty()&&Q.empty()) return;
	int st=++k[c];
	vector<int> lP,rP,lQ,rQ,cP;
	for(int i: P){
		ll v=a[i][c]>>bit;
		if(v==1) cP.emplace_back(i);
		else if(v&1) rP.emplace_back(i);
		else lP.emplace_back(i);
	}
	for(int i: Q){
		ll v=b[i][c]>>bit;
		if(v==1) dfn[i][c]=st;
		else if(v&1) rQ.emplace_back(i);
		else lQ.emplace_back(i);
	}
	build(bit+1,c,lP,lQ); build(bit+1,c,rP,rQ);
	int en=k[c];
	for(int i: cP){
		in[i][c]=st;
		out[i][c]=en;
	}
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>q;
	pw[0]=1;
	for(int i=1;i<=60;i++) pw[i]=pw[i-1]*2;
	for(int i=1;i<=n;i++){
		cin>>a[i][0]>>a[i][1]>>v[i];
		while(pw[c[i][0]+1]<=a[i][0]) c[i][0]++;
		while(pw[c[i][1]+1]<=a[i][1]) c[i][1]++;
	}
	for(int i=1;i<=q;i++){
		cin>>b[i][0]>>b[i][1];
		while(pw[d[i][0]+1]<=b[i][0]) d[i][0]++;
		while(pw[d[i][1]+1]<=b[i][1]) d[i][1]++;
	}
	vector<int> P(n),Q(q);
	for(int i=1;i<=n;i++) P[i-1]=i;
	for(int i=1;i<=q;i++) Q[i-1]=i;
	build(0,0,P,Q); build(0,1,P,Q);
	for(int i=1;i<=n;i++){
		ev[2*i-1]={in[i][0],in[i][1],out[i][1],v[i]};
		ev[2*i]={out[i][0]+1,in[i][1],out[i][1],-v[i]};
	}
	sort(ev+1,ev+2*n+1);
	for(int i=1;i<=q;i++) idx[i]=i;
	sort(idx+1,idx+q+1,[&](int i,int j){
		return dfn[i][0]<dfn[j][0];
	});
	for(int i=1,j=1;j<=q;j++){
		while(i<=2*n&&ev[i][0]<=dfn[idx[j]][0]){
			F.upd(ev[i][1],ev[i][3]);
			F.upd(ev[i][2]+1,-ev[i][3]);
			i++;
		}
		ans[idx[j]]=F.qry(dfn[idx[j]][1]);
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 24 ms 1136 KB Output is correct
3 Correct 24 ms 1084 KB Output is correct
4 Correct 22 ms 1108 KB Output is correct
5 Correct 21 ms 1060 KB Output is correct
6 Correct 15 ms 1112 KB Output is correct
7 Correct 15 ms 1072 KB Output is correct
8 Correct 15 ms 1056 KB Output is correct
9 Correct 15 ms 1052 KB Output is correct
10 Correct 15 ms 1064 KB Output is correct
11 Correct 15 ms 1068 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1959 ms 30848 KB Output is correct
2 Correct 1872 ms 30832 KB Output is correct
3 Correct 1756 ms 31616 KB Output is correct
4 Correct 1777 ms 31744 KB Output is correct
5 Correct 1016 ms 31616 KB Output is correct
6 Correct 986 ms 31588 KB Output is correct
7 Correct 998 ms 31636 KB Output is correct
8 Correct 985 ms 31660 KB Output is correct
9 Correct 1000 ms 31552 KB Output is correct
10 Correct 1054 ms 31536 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 480 ms 20724 KB Output is correct
3 Correct 469 ms 20720 KB Output is correct
4 Correct 403 ms 20848 KB Output is correct
5 Correct 439 ms 21680 KB Output is correct
6 Correct 260 ms 18064 KB Output is correct
7 Correct 261 ms 17628 KB Output is correct
8 Correct 264 ms 18132 KB Output is correct
9 Correct 260 ms 18664 KB Output is correct
10 Correct 275 ms 18060 KB Output is correct
11 Correct 260 ms 18128 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 24 ms 1136 KB Output is correct
3 Correct 24 ms 1084 KB Output is correct
4 Correct 22 ms 1108 KB Output is correct
5 Correct 21 ms 1060 KB Output is correct
6 Correct 15 ms 1112 KB Output is correct
7 Correct 15 ms 1072 KB Output is correct
8 Correct 15 ms 1056 KB Output is correct
9 Correct 15 ms 1052 KB Output is correct
10 Correct 15 ms 1064 KB Output is correct
11 Correct 15 ms 1068 KB Output is correct
12 Correct 1959 ms 30848 KB Output is correct
13 Correct 1872 ms 30832 KB Output is correct
14 Correct 1756 ms 31616 KB Output is correct
15 Correct 1777 ms 31744 KB Output is correct
16 Correct 1016 ms 31616 KB Output is correct
17 Correct 986 ms 31588 KB Output is correct
18 Correct 998 ms 31636 KB Output is correct
19 Correct 985 ms 31660 KB Output is correct
20 Correct 1000 ms 31552 KB Output is correct
21 Correct 1054 ms 31536 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 480 ms 20724 KB Output is correct
24 Correct 469 ms 20720 KB Output is correct
25 Correct 403 ms 20848 KB Output is correct
26 Correct 439 ms 21680 KB Output is correct
27 Correct 260 ms 18064 KB Output is correct
28 Correct 261 ms 17628 KB Output is correct
29 Correct 264 ms 18132 KB Output is correct
30 Correct 260 ms 18664 KB Output is correct
31 Correct 275 ms 18060 KB Output is correct
32 Correct 260 ms 18128 KB Output is correct
33 Correct 2295 ms 63620 KB Output is correct
34 Correct 2421 ms 63540 KB Output is correct
35 Correct 1958 ms 67004 KB Output is correct
36 Correct 2120 ms 64448 KB Output is correct
37 Correct 1348 ms 53860 KB Output is correct
38 Correct 1395 ms 54064 KB Output is correct
39 Correct 1368 ms 54040 KB Output is correct
40 Correct 1357 ms 54064 KB Output is correct
41 Correct 1289 ms 55376 KB Output is correct
42 Correct 1293 ms 53992 KB Output is correct