oj.uz

Submission #814351

# Submission time Handle Problem Language Result Execution time Memory
814351 2023-08-08T07:00:13 Z 이종영(#10372) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 655 ms 272780 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll=long long;
using pii=array<int,2>;
using ti4=array<int,4>;
const ll inf=1e18;
const int N=50005;
int r,c,n,q,x[2*N],y[2*N],nx,ny;
ll prv,m;
ti4 a[N];
vector<pii> ev1[2*N],ev2[2*N];
struct node{
	int l=0,r=0,a=0,sa=0;
	ll b=0,sb=0;
};
vector<node> T;
int roots[2*N];
void upd(int n1,int n2,int l,int r,int s,int e,ll v1,ll v2){
	if(r<s||e<l) assert(0);
	T[n2]=T[n1];
	ll d=r-l+1;
	if(s<=l&&r<=e){
		T[n2].a+=v1;
		T[n2].sa+=v1*d;
		T[n2].b+=v2;
		T[n2].sb+=v2*d;
		return;
	}
	int m=(l+r)>>1;
	if(s<=m){
		T[n2].l=T.size(); T.emplace_back();
		T[T[n2].l]=T[T[n1].l];
		upd(T[n1].l,T[n2].l,l,m,s,e,v1,v2);
	}
	if(m<e){
		T[n2].r=T.size(); T.emplace_back();
		T[T[n2].r]=T[T[n1].r];
		upd(T[n1].r,T[n2].r,m+1,r,s,e,v1,v2);
	}
	T[n2].sa=T[T[n2].l].sa+T[T[n2].r].sa+T[n2].a*d;
	T[n2].sb=T[T[n2].l].sb+T[T[n2].r].sb+T[n2].b*d;
}
ll qry(int nd,int l,int r,int s,int e,ll x){
	if(!nd||r<s||e<l) return 0;
	if(s<=l&&r<=e) return T[nd].sa*x+T[nd].sb;
	int m=(l+r)>>1;
	ll val=qry(T[nd].l,l,m,s,e,x)+qry(T[nd].r,m+1,r,s,e,x);
	ll d=min(e,r)-max(l,s)+1;
	return val+T[nd].a*d*x+T[nd].b*d;
}
ll solve(int x1,int y1,int y2){
	if(x1<=x[1]) return 0;
	int i=upper_bound(x+1,x+nx+1,x1)-x-1;
	debug(i);
	return qry(roots[i],1,c,y1+1,y2,x1);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>r>>c>>n>>q>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2]>>a[i][3];
		swap(a[i][1],a[i][2]);
		if(a[i][0]>a[i][1]) swap(a[i][0],a[i][1]);
		if(a[i][2]>a[i][3]) swap(a[i][2],a[i][3]);
		x[2*i-1]=a[i][0];
		x[2*i]=a[i][1];
		y[2*i-1]=a[i][2];
		y[2*i]=a[i][3];
	}
	sort(x+1,x+2*n+1); nx=unique(x+1,x+2*n+1)-x-1;
	//sort(y+1,y+2*n+1); ny=unique(y+1,y+2*n+1)-y-1;
	for(int i=1;i<=n;i++){
		a[i][0]=lower_bound(x+1,x+nx+1,a[i][0])-x;
		a[i][1]=lower_bound(x+1,x+nx+1,a[i][1])-x;
		//a[i][2]=lower_bound(y+1,y+ny+1,a[i][2])-y;
		//a[i][3]=lower_bound(y+1,y+ny+1,a[i][3])-y;
		ev1[a[i][0]].push_back({a[i][2],a[i][3]});
		ev2[a[i][1]].push_back({a[i][2],a[i][3]});
	}
	for(int i=1;i<=nx;i++){
		roots[i]=T.size(); T.emplace_back();
		T[roots[i]]=T[roots[i-1]];
		for(auto [l,r]: ev1[i]){
			int nroot=T.size(); T.emplace_back();
			debug(x[i],l,r,1);
			upd(roots[i],nroot,1,c,l+1,r,1,-x[i]);
			roots[i]=nroot;
		}
		for(auto [l,r]: ev2[i]){
			int nroot=T.size(); T.emplace_back();
			debug(x[i],l,r,-1);
			upd(roots[i],nroot,1,c,l+1,r,-1,x[i]);
			roots[i]=nroot;
		}
		debug(qry(roots[i],1,c,1,c,x[i]));
	}
	for(int t=1;t<=q;t++){
		ll x1,y1,x2,y2,v;
		cin>>x1>>y1>>x2>>y2>>v;
		v=prv*v%m;
		x1+=v; if(x1>=m) x1-=m;
		x2+=v; if(x2>=m) x2-=m;
		y1+=v; if(y1>=m) y1-=m;
		y2+=v; if(y2>=m) y2-=m;
		if(x1>x2) swap(x1,x2);
		if(y1>y2) swap(y1,y2);
		ll ans=solve(x2,y1,y2)-solve(x1,y1,y2);
		cout<<ans<<"\n";
		prv=ans%m;
	}
	return 0;
}

Compilation message

Main.cpp: In function 'll solve(int, int, int)':
Main.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
Main.cpp:59:2: note: in expansion of macro 'debug'
   59 |  debug(i);
      |  ^~~~~
Main.cpp: In function 'int main()':
Main.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
Main.cpp:90:4: note: in expansion of macro 'debug'
   90 |    debug(x[i],l,r,1);
      |    ^~~~~
Main.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
Main.cpp:96:4: note: in expansion of macro 'debug'
   96 |    debug(x[i],l,r,-1);
      |    ^~~~~
Main.cpp:6:20: warning: statement has no effect [-Wunused-value]
    6 | #define debug(...) 42
      |                    ^~
Main.cpp:100:3: note: in expansion of macro 'debug'
  100 |   debug(qry(roots[i],1,c,1,c,x[i]));
      |   ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 17 ms 13708 KB Output is correct
5 Correct 17 ms 13760 KB Output is correct
6 Correct 22 ms 13632 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 17 ms 13708 KB Output is correct
5 Correct 17 ms 13760 KB Output is correct
6 Correct 22 ms 13632 KB Output is correct
7 Correct 191 ms 139956 KB Output is correct
8 Correct 449 ms 141028 KB Output is correct
9 Correct 272 ms 140260 KB Output is correct
10 Correct 397 ms 140972 KB Output is correct
11 Correct 281 ms 141132 KB Output is correct
12 Correct 295 ms 140676 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 17 ms 13708 KB Output is correct
5 Correct 17 ms 13760 KB Output is correct
6 Correct 22 ms 13632 KB Output is correct
7 Correct 207 ms 140944 KB Output is correct
8 Correct 433 ms 141384 KB Output is correct
9 Correct 285 ms 140288 KB Output is correct
10 Correct 364 ms 141412 KB Output is correct
11 Correct 257 ms 141444 KB Output is correct
12 Correct 310 ms 141076 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 4 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 17 ms 13708 KB Output is correct
5 Correct 17 ms 13760 KB Output is correct
6 Correct 22 ms 13632 KB Output is correct
7 Correct 191 ms 139956 KB Output is correct
8 Correct 449 ms 141028 KB Output is correct
9 Correct 272 ms 140260 KB Output is correct
10 Correct 397 ms 140972 KB Output is correct
11 Correct 281 ms 141132 KB Output is correct
12 Correct 295 ms 140676 KB Output is correct
13 Correct 207 ms 140944 KB Output is correct
14 Correct 433 ms 141384 KB Output is correct
15 Correct 285 ms 140288 KB Output is correct
16 Correct 364 ms 141412 KB Output is correct
17 Correct 257 ms 141444 KB Output is correct
18 Correct 310 ms 141076 KB Output is correct
19 Correct 364 ms 272276 KB Output is correct
20 Correct 626 ms 272740 KB Output is correct
21 Correct 418 ms 271548 KB Output is correct
22 Correct 594 ms 272656 KB Output is correct
23 Correct 310 ms 141316 KB Output is correct
24 Correct 453 ms 272432 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 73640 KB Output is correct
2 Correct 417 ms 140420 KB Output is correct
3 Correct 257 ms 140328 KB Output is correct
4 Correct 378 ms 140596 KB Output is correct
5 Correct 256 ms 74828 KB Output is correct
6 Correct 294 ms 140484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 73640 KB Output is correct
2 Correct 417 ms 140420 KB Output is correct
3 Correct 257 ms 140328 KB Output is correct
4 Correct 378 ms 140596 KB Output is correct
5 Correct 256 ms 74828 KB Output is correct
6 Correct 294 ms 140484 KB Output is correct
7 Correct 409 ms 272232 KB Output is correct
8 Correct 655 ms 272668 KB Output is correct
9 Correct 430 ms 271532 KB Output is correct
10 Correct 602 ms 272780 KB Output is correct
11 Correct 299 ms 141380 KB Output is correct
12 Correct 445 ms 272420 KB Output is correct