oj.uz

Submission #951434

# Submission time Handle Problem Language Result Execution time Memory
951434 2024-03-22T00:19:41 Z djs100201 Seats (IOI18_seats) C++17
100 / 100
 1890 ms 235388 KB 
#include<bits/stdc++.h>
#include "seats.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = int;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =2e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
vector<vector<int>>arr,bit;
vector<int>F,S,N,M;
struct node{
	P val;
	int cnt;
};
node merge(node a, node b){
	node ret=a;
	if(a.val==b.val){
		ret.cnt+=b.cnt;
		return ret;
	}
	if(a.val<b.val)return ret;
	return b;
}
P add(P a,P b){
	return {a.first+b.first,a.second+b.second};
}
class lazy_seg{
	public:
	vector<node> tree;
	vector<P>lazy;
	void start(int n)
	{
		// 0~n까지 쓰겠다.
		tree.resize(n * 4);
		lazy.resize(n * 4);
	}
	node init(ll N, ll s, ll e)
	{
		if (s == e){
			tree[N].val={F[s],S[s]};
			tree[N].cnt=1;
			return tree[N];
        }
		ll mid = (s + e) / 2;
		return tree[N] = merge(init(N * 2, s, mid) , init(N * 2 + 1, mid + 1, e));
	}
	void update_lazy(ll N, ll s, ll e)
	{
		if (lazy[N].first==0 && lazy[N].second==0)return;
		tree[N].val=add(tree[N].val,lazy[N]);
		if (s != e)
		{	
			lazy[N*2]=add(lazy[N*2],lazy[N]);
			lazy[N*2+1]=add(lazy[N*2+1],lazy[N]);
		}
		lazy[N] = {0,0};
	}
	void update(ll N, ll s, ll e, ll l, ll r, P val)
	{
		update_lazy(N, s, e);
		if (l > e || r < s)
			return;
		if (l <= s && e <= r)
		{
			lazy[N] = val;
			update_lazy(N, s, e);
			return;
		}
		ll mid = (s + e) / 2;
		update(N * 2, s, mid, l, r, val);
		update(N * 2 + 1, mid + 1, e, l, r, val);
		tree[N]=merge(tree[N*2],tree[N*2+1]);
	}
};
void pre_init(int y,int x){
	if(y==0){
		if(x==0){
			F[arr[y][x]]++;
		}
		else if(x==m){
			F[arr[y][x-1]]++;
		}
		else{
			int l=arr[y][x-1],r=arr[y][x];
			F[min(l,r)]++,F[max(l,r)]--;
		}
	}
	else if(y==n){
		if(x==0){
			F[arr[y-1][x]]++;
		}
		else if(x==m){
			F[arr[y-1][x-1]]++;
		}
		else{
			int l=arr[y-1][x-1],r=arr[y-1][x];
			F[min(l,r)]++,F[max(l,r)]--;
		}
	}
	else if(x==0){
		int u=arr[y-1][x],d=arr[y][x];
		F[min(u,d)]++,F[max(u,d)]--;
	}
	else if(x==m){
		int u=arr[y-1][x-1],d=arr[y][x-1];
		F[min(u,d)]++,F[max(u,d)]--;
	}
	else{
		//이때부터는 꼭짓점에 인접한 타일이 항상 4개 있는경우 크기에 따라서 정렬해두자.
		/*
		[0,1]
		[2,3]
		순서임
		*/
		vector<P>T;
		T.push_back({arr[y-1][x-1],0});
		T.push_back({arr[y-1][x],1});
		T.push_back({arr[y][x],2});
		T.push_back({arr[y][x-1],3});
		sort(all(T));
		ll ff=0;
		for(int i=0;i<4;i++){
			auto [a,b]=T[i];
			if(i==0)F[a]++;
			else if(i==1){
				F[a]--;
				if((T[0].second^T[1].second)==2){
					//마주보는 경우
					F[a]+=2;
					ff=2;
				}
			}
			else if(i==2){
				F[a]-=ff;
				S[a]++;
			}
			else S[a]--;
		}
	}
 
}
lazy_seg seg;
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	bit.resize(H+1);
	for(int i=0;i<=H;i++)bit[i].resize(W+1);
	arr.resize(H);
	for(int i=0;i<H;i++)arr[i].resize(W);
	n=H,m=W;
	N=R,M=C;
  	R.clear(),C.clear();
	F.clear(),S.clear();
	F.resize(n*m),S.resize(n*m);
	//First값과 Second값의 PrefixSum
	for(int i=0;i<n*m;i++)arr[R[i]][C[i]]=i;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			pre_init(i,j);
	for(int i=0;i<n*m;i++){
		if(i)F[i]+=F[i-1],S[i]+=S[i-1];
	}
	seg.start(n*m);
	seg.init(1,0,n*m-1);
}
void query(int y,int x,int val){
	if(val<0 && bit[y][x])return;
	if(val>0 && !bit[y][x])return;
	bit[y][x]^=1;
	if(y==0){
		if(x==0){
			seg.update(1,0,n*m-1,arr[y][x],n*m-1,{val,0});
		}
		else if(x==m){
			seg.update(1,0,n*m-1,arr[y][x-1],n*m-1,{val,0});
		}
		else{
			int l=arr[y][x-1],r=arr[y][x];
			if(l>r)swap(l,r);
			seg.update(1,0,n*m-1,l,r-1,{val,0});
		}
	}
	else if(y==n){
		if(x==0){
			seg.update(1,0,n*m-1,arr[y-1][x],n*m-1,{val,0});
		}
		else if(x==m){
			seg.update(1,0,n*m-1,arr[y-1][x-1],n*m-1,{val,0});
		}
		else{
			int l=arr[y-1][x-1],r=arr[y-1][x];
			if(l>r)swap(l,r);
			seg.update(1,0,n*m-1,l,r-1,{val,0});
		}
	}
	else if(x==0){
		int u=arr[y-1][x],d=arr[y][x];
		if(d>u)swap(u,d);
		seg.update(1,0,n*m-1,d,u-1,{val,0});
	}
	else if(x==m){
		int u=arr[y-1][x-1],d=arr[y][x-1];
		if(d>u)swap(u,d);
		seg.update(1,0,n*m-1,d,u-1,{val,0});
	}
	else{
		//이때부터는 꼭짓점에 인접한 타일이 항상 4개 있는경우 크기에 따라서 정렬해두자.
		/*
		[0,1]
		[2,3]
		순서임
		*/
		vector<P>T;
		T.push_back({arr[y-1][x-1],0});
		T.push_back({arr[y-1][x],1});
		T.push_back({arr[y][x],2});
		T.push_back({arr[y][x-1],3});
		sort(all(T));
		seg.update(1,0,n*m-1,T[0].first,T[1].first-1,{val,0});
		if((T[0].second^T[1].second)==2){
			seg.update(1,0,n*m-1,T[1].first,T[2].first-1,{val*2,0});
		}
		seg.update(1,0,n*m-1,T[2].first,T[3].first-1,{0,val});
	}
 
}
int swap_seats(int a, int b) {
	query(N[a],M[a],-1);
	query(N[a]+1,M[a],-1);
	query(N[a]+1,M[a]+1,-1);
	query(N[a],M[a]+1,-1);
	
	query(N[b],M[b],-1);
	query(N[b]+1,M[b],-1);
	query(N[b]+1,M[b]+1,-1);
	query(N[b],M[b]+1,-1);
 
	arr[N[a]][M[a]]=b;
	arr[N[b]][M[b]]=a;
	swap(N[a],N[b]);
	swap(M[a],M[b]);
	
	query(N[a],M[a],1);
	query(N[a]+1,M[a],1);
	query(N[a]+1,M[a]+1,1);
	query(N[a],M[a]+1,1);
	
	query(N[b],M[b],1);
	query(N[b]+1,M[b],1);
	query(N[b]+1,M[b]+1,1);
	query(N[b],M[b]+1,1);
	P rec={4,0};
	if(seg.tree[1].val==rec)return seg.tree[1].cnt;
	else return 0;
}

Compilation message

seats.cpp:12:37: warning: integer overflow in expression of type 'll' {aka 'int'} results in '1321730048' [-Woverflow]
   12 | const ll n_ =2e5+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
      |                             ~~~~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 348 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 41 ms 548 KB Output is correct
4 Correct 16 ms 592 KB Output is correct
5 Correct 12 ms 604 KB Output is correct
6 Correct 28 ms 604 KB Output is correct
7 Correct 32 ms 600 KB Output is correct
8 Correct 28 ms 596 KB Output is correct
9 Correct 28 ms 596 KB Output is correct
10 Correct 34 ms 600 KB Output is correct
11 Correct 30 ms 592 KB Output is correct
12 Correct 13 ms 604 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 348 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 41 ms 548 KB Output is correct
4 Correct 16 ms 592 KB Output is correct
5 Correct 12 ms 604 KB Output is correct
6 Correct 28 ms 604 KB Output is correct
7 Correct 32 ms 600 KB Output is correct
8 Correct 28 ms 596 KB Output is correct
9 Correct 28 ms 596 KB Output is correct
10 Correct 34 ms 600 KB Output is correct
11 Correct 30 ms 592 KB Output is correct
12 Correct 13 ms 604 KB Output is correct
13 Correct 75 ms 1840 KB Output is correct
14 Correct 88 ms 1832 KB Output is correct
15 Correct 33 ms 1880 KB Output is correct
16 Correct 24 ms 2652 KB Output is correct
17 Correct 52 ms 1628 KB Output is correct
18 Correct 51 ms 1628 KB Output is correct
19 Correct 47 ms 1880 KB Output is correct
20 Correct 37 ms 2140 KB Output is correct
21 Correct 25 ms 1880 KB Output is correct
22 Correct 25 ms 2652 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 117820 KB Output is correct
2 Correct 365 ms 133204 KB Output is correct
3 Correct 354 ms 133200 KB Output is correct
4 Correct 357 ms 133204 KB Output is correct
5 Correct 382 ms 133100 KB Output is correct
6 Correct 342 ms 133284 KB Output is correct
7 Correct 338 ms 133332 KB Output is correct
8 Correct 353 ms 133372 KB Output is correct
9 Correct 387 ms 133180 KB Output is correct
10 Correct 351 ms 133552 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 1664 KB Output is correct
2 Correct 97 ms 12116 KB Output is correct
3 Correct 358 ms 133128 KB Output is correct
4 Correct 492 ms 133164 KB Output is correct
5 Correct 225 ms 137040 KB Output is correct
6 Correct 440 ms 235388 KB Output is correct
7 Correct 308 ms 134992 KB Output is correct
8 Correct 355 ms 133716 KB Output is correct
9 Correct 371 ms 134460 KB Output is correct
10 Correct 389 ms 141628 KB Output is correct
11 Correct 325 ms 180656 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1496 KB Output is correct
2 Correct 69 ms 1744 KB Output is correct
3 Correct 121 ms 2000 KB Output is correct
4 Correct 169 ms 2104 KB Output is correct
5 Correct 311 ms 3276 KB Output is correct
6 Correct 632 ms 138068 KB Output is correct
7 Correct 629 ms 137892 KB Output is correct
8 Correct 607 ms 137952 KB Output is correct
9 Correct 810 ms 137808 KB Output is correct
10 Correct 527 ms 137964 KB Output is correct
11 Correct 517 ms 137808 KB Output is correct
12 Correct 515 ms 137904 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 348 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 41 ms 548 KB Output is correct
4 Correct 16 ms 592 KB Output is correct
5 Correct 12 ms 604 KB Output is correct
6 Correct 28 ms 604 KB Output is correct
7 Correct 32 ms 600 KB Output is correct
8 Correct 28 ms 596 KB Output is correct
9 Correct 28 ms 596 KB Output is correct
10 Correct 34 ms 600 KB Output is correct
11 Correct 30 ms 592 KB Output is correct
12 Correct 13 ms 604 KB Output is correct
13 Correct 75 ms 1840 KB Output is correct
14 Correct 88 ms 1832 KB Output is correct
15 Correct 33 ms 1880 KB Output is correct
16 Correct 24 ms 2652 KB Output is correct
17 Correct 52 ms 1628 KB Output is correct
18 Correct 51 ms 1628 KB Output is correct
19 Correct 47 ms 1880 KB Output is correct
20 Correct 37 ms 2140 KB Output is correct
21 Correct 25 ms 1880 KB Output is correct
22 Correct 25 ms 2652 KB Output is correct
23 Correct 525 ms 117820 KB Output is correct
24 Correct 365 ms 133204 KB Output is correct
25 Correct 354 ms 133200 KB Output is correct
26 Correct 357 ms 133204 KB Output is correct
27 Correct 382 ms 133100 KB Output is correct
28 Correct 342 ms 133284 KB Output is correct
29 Correct 338 ms 133332 KB Output is correct
30 Correct 353 ms 133372 KB Output is correct
31 Correct 387 ms 133180 KB Output is correct
32 Correct 351 ms 133552 KB Output is correct
33 Correct 73 ms 1664 KB Output is correct
34 Correct 97 ms 12116 KB Output is correct
35 Correct 358 ms 133128 KB Output is correct
36 Correct 492 ms 133164 KB Output is correct
37 Correct 225 ms 137040 KB Output is correct
38 Correct 440 ms 235388 KB Output is correct
39 Correct 308 ms 134992 KB Output is correct
40 Correct 355 ms 133716 KB Output is correct
41 Correct 371 ms 134460 KB Output is correct
42 Correct 389 ms 141628 KB Output is correct
43 Correct 325 ms 180656 KB Output is correct
44 Correct 26 ms 1496 KB Output is correct
45 Correct 69 ms 1744 KB Output is correct
46 Correct 121 ms 2000 KB Output is correct
47 Correct 169 ms 2104 KB Output is correct
48 Correct 311 ms 3276 KB Output is correct
49 Correct 632 ms 138068 KB Output is correct
50 Correct 629 ms 137892 KB Output is correct
51 Correct 607 ms 137952 KB Output is correct
52 Correct 810 ms 137808 KB Output is correct
53 Correct 527 ms 137964 KB Output is correct
54 Correct 517 ms 137808 KB Output is correct
55 Correct 515 ms 137904 KB Output is correct
56 Correct 118 ms 2000 KB Output is correct
57 Correct 373 ms 2132 KB Output is correct
58 Correct 524 ms 3308 KB Output is correct
59 Correct 1315 ms 134732 KB Output is correct
60 Correct 1890 ms 134732 KB Output is correct
61 Correct 998 ms 134832 KB Output is correct
62 Correct 770 ms 136796 KB Output is correct
63 Correct 1507 ms 136156 KB Output is correct
64 Correct 1169 ms 135232 KB Output is correct
65 Correct 985 ms 134740 KB Output is correct
66 Correct 1266 ms 135580 KB Output is correct
67 Correct 1136 ms 142416 KB Output is correct
68 Correct 855 ms 163352 KB Output is correct
69 Correct 1442 ms 181840 KB Output is correct