oj.uz

Submission #814345

# Submission time Handle Problem Language Result Execution time Memory
814345 2023-08-08T06:58:48 Z 이종영(#10372) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 617 ms 272868 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;
	}
	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 5 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 5 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 21 ms 13632 KB Output is correct
5 Correct 17 ms 13680 KB Output is correct
6 Correct 17 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 5 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 21 ms 13632 KB Output is correct
5 Correct 17 ms 13680 KB Output is correct
6 Correct 17 ms 13632 KB Output is correct
7 Correct 189 ms 140008 KB Output is correct
8 Correct 440 ms 141080 KB Output is correct
9 Correct 265 ms 140460 KB Output is correct
10 Correct 398 ms 141192 KB Output is correct
11 Correct 307 ms 141308 KB Output is correct
12 Correct 298 ms 140832 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 5 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 21 ms 13632 KB Output is correct
5 Correct 17 ms 13680 KB Output is correct
6 Correct 17 ms 13632 KB Output is correct
7 Correct 204 ms 141096 KB Output is correct
8 Correct 467 ms 141480 KB Output is correct
9 Correct 273 ms 140376 KB Output is correct
10 Correct 430 ms 141492 KB Output is correct
11 Correct 265 ms 141620 KB Output is correct
12 Correct 286 ms 141216 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 5 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 21 ms 13632 KB Output is correct
5 Correct 17 ms 13680 KB Output is correct
6 Correct 17 ms 13632 KB Output is correct
7 Correct 189 ms 140008 KB Output is correct
8 Correct 440 ms 141080 KB Output is correct
9 Correct 265 ms 140460 KB Output is correct
10 Correct 398 ms 141192 KB Output is correct
11 Correct 307 ms 141308 KB Output is correct
12 Correct 298 ms 140832 KB Output is correct
13 Correct 204 ms 141096 KB Output is correct
14 Correct 467 ms 141480 KB Output is correct
15 Correct 273 ms 140376 KB Output is correct
16 Correct 430 ms 141492 KB Output is correct
17 Correct 265 ms 141620 KB Output is correct
18 Correct 286 ms 141216 KB Output is correct
19 Correct 378 ms 272408 KB Output is correct
20 Correct 617 ms 272868 KB Output is correct
21 Correct 408 ms 271768 KB Output is correct
22 Correct 526 ms 272836 KB Output is correct
23 Correct 309 ms 141480 KB Output is correct
24 Correct 481 ms 272704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 73740 KB Output is correct
2 Correct 446 ms 140516 KB Output is correct
3 Correct 252 ms 140212 KB Output is correct
4 Correct 371 ms 140620 KB Output is correct
5 Correct 272 ms 74868 KB Output is correct
6 Correct 298 ms 140368 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 73740 KB Output is correct
2 Correct 446 ms 140516 KB Output is correct
3 Correct 252 ms 140212 KB Output is correct
4 Correct 371 ms 140620 KB Output is correct
5 Correct 272 ms 74868 KB Output is correct
6 Correct 298 ms 140368 KB Output is correct
7 Incorrect 426 ms 272316 KB Output isn't correct
8 Halted 0 ms 0 KB -