oj.uz

Submission #951426

# Submission time Handle Problem Language Result Execution time Memory
951426 2024-03-22T00:03:38 Z djs100201 Seats (IOI18_seats) C++17
5 / 100
 444 ms 205632 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);
}
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,A;
	vector<P>lazy;
	void start(int n)
	{
		// 0~n까지 쓰겠다.
		tree.resize(n * 2 + 100);
		lazy.resize(n * 2 + 100);
		A.resize(n * 2 + 100);
	}
	node init(ll N, ll s, ll e)
	{
		if (s == e)return tree[N]=A[s];
		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]);
	}
};
vector<vector<int>>arr,bit;
vector<int>F,S,N,M;
ll lim;
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();
	seg.start(n*m);
	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.A[i].val={F[i],S[i]};
		seg.A[i].cnt=1;
	}
	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 592 KB Output is correct
2 Correct 21 ms 564 KB Output is correct
3 Correct 42 ms 596 KB Output is correct
4 Correct 15 ms 600 KB Output is correct
5 Correct 13 ms 600 KB Output is correct
6 Correct 29 ms 592 KB Output is correct
7 Correct 33 ms 568 KB Output is correct
8 Correct 28 ms 596 KB Output is correct
9 Correct 28 ms 596 KB Output is correct
10 Correct 33 ms 596 KB Output is correct
11 Correct 29 ms 596 KB Output is correct
12 Correct 13 ms 604 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 592 KB Output is correct
2 Correct 21 ms 564 KB Output is correct
3 Correct 42 ms 596 KB Output is correct
4 Correct 15 ms 600 KB Output is correct
5 Correct 13 ms 600 KB Output is correct
6 Correct 29 ms 592 KB Output is correct
7 Correct 33 ms 568 KB Output is correct
8 Correct 28 ms 596 KB Output is correct
9 Correct 28 ms 596 KB Output is correct
10 Correct 33 ms 596 KB Output is correct
11 Correct 29 ms 596 KB Output is correct
12 Correct 13 ms 604 KB Output is correct
13 Runtime error 6 ms 2736 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 444 ms 205632 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 2904 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2264 KB Output is correct
2 Correct 69 ms 2068 KB Output is correct
3 Correct 132 ms 1916 KB Output is correct
4 Correct 179 ms 2264 KB Output is correct
5 Runtime error 21 ms 4180 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 592 KB Output is correct
2 Correct 21 ms 564 KB Output is correct
3 Correct 42 ms 596 KB Output is correct
4 Correct 15 ms 600 KB Output is correct
5 Correct 13 ms 600 KB Output is correct
6 Correct 29 ms 592 KB Output is correct
7 Correct 33 ms 568 KB Output is correct
8 Correct 28 ms 596 KB Output is correct
9 Correct 28 ms 596 KB Output is correct
10 Correct 33 ms 596 KB Output is correct
11 Correct 29 ms 596 KB Output is correct
12 Correct 13 ms 604 KB Output is correct
13 Runtime error 6 ms 2736 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -