oj.uz

Submission #349299

# Submission time Handle Problem Language Result Execution time Memory
349299 2021-01-17T11:11:44 Z Kerim Seats (IOI18_seats) C++17
100 / 100
 1422 ms 123144 KB 
#include "seats.h"
#include "bits/stdc++.h"
#define MAXN 1000009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<int>r,c,delta;
vector<vector<int> >arr;
int h,w,hw;
struct node{
	int mn,sum,cnt;	
}s[MAXN<<2];
node merge(node x,node y){
	node z;z.sum=x.sum+y.sum;z.cnt=0;
	z.mn=min(x.mn,x.sum+y.mn);
	if(x.mn==z.mn)z.cnt+=x.cnt;
	if(x.sum+y.mn==z.mn)z.cnt+=y.cnt;
	return z;	
}
void upd(int p,int v,int nd=1,int x=0,int y=hw-1){
	if(x==y){s[nd].sum=s[nd].mn=v;s[nd].cnt=1;return;}
	int mid=(x+y)>>1;
	if(p<=mid)upd(p,v,nd<<1,x,mid);
	else upd(p,v,nd<<1|1,mid+1,y);
	s[nd]=merge(s[nd<<1],s[nd<<1|1]);
}
void add(int val){
	if(val<0 or val>=hw)return;
	delta[val]=0;
	int x=r[val],y=c[val];
	for(int a=0;a<=1;a++)
		for(int b=0;b<=1;b++){
			int cnt=0;
			for(int i=0;i<=1;i++)
				for(int j=0;j<=1;j++)
					if(arr[x-1+a+i][y-1+b+j]>val)cnt++;
			if(cnt&1)delta[val]++;
			else delta[val]--;
		}
	upd(val,delta[val]);
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C) {
  	r=R;c=C;h=H;w=W;hw=H*W;
  	arr.resize(h+2);delta.resize(hw+2);
  	for(int i=0;i<=h+1;i++)
  		arr[i].resize(w+2);
  	for(int i=0;i<=h+1;i++)
  		for(int j=0;j<=w+1;j++)
  			arr[i][j]=hw;
  	for(int i=0;i<hw;i++)
		arr[++r[i]][++c[i]]=i;
  	for(int i=0;i<hw;i++)add(i);
}
int swap_seats(int a, int b) {
	swap(arr[r[a]][c[a]],arr[r[b]][c[b]]);
	swap(c[a],c[b]);swap(r[a],r[b]);
	for(int i=-1;i<=1;i++)
		for(int j=-1;j<=1;j++)
			add(arr[r[a]+i][c[a]+j]),add(arr[r[b]+i][c[b]+j]);
	return s[1].cnt;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 492 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 14 ms 492 KB Output is correct
4 Correct 6 ms 492 KB Output is correct
5 Correct 6 ms 492 KB Output is correct
6 Correct 11 ms 492 KB Output is correct
7 Correct 12 ms 492 KB Output is correct
8 Correct 13 ms 492 KB Output is correct
9 Correct 13 ms 492 KB Output is correct
10 Correct 12 ms 492 KB Output is correct
11 Correct 11 ms 492 KB Output is correct
12 Correct 6 ms 492 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 492 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 14 ms 492 KB Output is correct
4 Correct 6 ms 492 KB Output is correct
5 Correct 6 ms 492 KB Output is correct
6 Correct 11 ms 492 KB Output is correct
7 Correct 12 ms 492 KB Output is correct
8 Correct 13 ms 492 KB Output is correct
9 Correct 13 ms 492 KB Output is correct
10 Correct 12 ms 492 KB Output is correct
11 Correct 11 ms 492 KB Output is correct
12 Correct 6 ms 492 KB Output is correct
13 Correct 30 ms 1260 KB Output is correct
14 Correct 31 ms 1260 KB Output is correct
15 Correct 16 ms 1408 KB Output is correct
16 Correct 14 ms 1772 KB Output is correct
17 Correct 23 ms 1388 KB Output is correct
18 Correct 28 ms 1260 KB Output is correct
19 Correct 26 ms 1388 KB Output is correct
20 Correct 21 ms 1516 KB Output is correct
21 Correct 14 ms 1388 KB Output is correct
22 Correct 15 ms 1772 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 56544 KB Output is correct
2 Correct 679 ms 72300 KB Output is correct
3 Correct 633 ms 72428 KB Output is correct
4 Correct 641 ms 72332 KB Output is correct
5 Correct 654 ms 72336 KB Output is correct
6 Correct 649 ms 72352 KB Output is correct
7 Correct 629 ms 72384 KB Output is correct
8 Correct 682 ms 72428 KB Output is correct
9 Correct 636 ms 72300 KB Output is correct
10 Correct 637 ms 72460 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 1536 KB Output is correct
2 Correct 92 ms 7532 KB Output is correct
3 Correct 652 ms 72312 KB Output is correct
4 Correct 781 ms 72300 KB Output is correct
5 Correct 610 ms 80236 KB Output is correct
6 Correct 1107 ms 123144 KB Output is correct
7 Correct 650 ms 74928 KB Output is correct
8 Correct 705 ms 72464 KB Output is correct
9 Correct 649 ms 72940 KB Output is correct
10 Correct 665 ms 77036 KB Output is correct
11 Correct 659 ms 95724 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1768 KB Output is correct
2 Correct 45 ms 1768 KB Output is correct
3 Correct 59 ms 1896 KB Output is correct
4 Correct 71 ms 2152 KB Output is correct
5 Correct 104 ms 3104 KB Output is correct
6 Correct 792 ms 64492 KB Output is correct
7 Correct 827 ms 64620 KB Output is correct
8 Correct 782 ms 65516 KB Output is correct
9 Correct 959 ms 64620 KB Output is correct
10 Correct 741 ms 64492 KB Output is correct
11 Correct 749 ms 64492 KB Output is correct
12 Correct 736 ms 64492 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 492 KB Output is correct
2 Correct 10 ms 492 KB Output is correct
3 Correct 14 ms 492 KB Output is correct
4 Correct 6 ms 492 KB Output is correct
5 Correct 6 ms 492 KB Output is correct
6 Correct 11 ms 492 KB Output is correct
7 Correct 12 ms 492 KB Output is correct
8 Correct 13 ms 492 KB Output is correct
9 Correct 13 ms 492 KB Output is correct
10 Correct 12 ms 492 KB Output is correct
11 Correct 11 ms 492 KB Output is correct
12 Correct 6 ms 492 KB Output is correct
13 Correct 30 ms 1260 KB Output is correct
14 Correct 31 ms 1260 KB Output is correct
15 Correct 16 ms 1408 KB Output is correct
16 Correct 14 ms 1772 KB Output is correct
17 Correct 23 ms 1388 KB Output is correct
18 Correct 28 ms 1260 KB Output is correct
19 Correct 26 ms 1388 KB Output is correct
20 Correct 21 ms 1516 KB Output is correct
21 Correct 14 ms 1388 KB Output is correct
22 Correct 15 ms 1772 KB Output is correct
23 Correct 796 ms 56544 KB Output is correct
24 Correct 679 ms 72300 KB Output is correct
25 Correct 633 ms 72428 KB Output is correct
26 Correct 641 ms 72332 KB Output is correct
27 Correct 654 ms 72336 KB Output is correct
28 Correct 649 ms 72352 KB Output is correct
29 Correct 629 ms 72384 KB Output is correct
30 Correct 682 ms 72428 KB Output is correct
31 Correct 636 ms 72300 KB Output is correct
32 Correct 637 ms 72460 KB Output is correct
33 Correct 31 ms 1536 KB Output is correct
34 Correct 92 ms 7532 KB Output is correct
35 Correct 652 ms 72312 KB Output is correct
36 Correct 781 ms 72300 KB Output is correct
37 Correct 610 ms 80236 KB Output is correct
38 Correct 1107 ms 123144 KB Output is correct
39 Correct 650 ms 74928 KB Output is correct
40 Correct 705 ms 72464 KB Output is correct
41 Correct 649 ms 72940 KB Output is correct
42 Correct 665 ms 77036 KB Output is correct
43 Correct 659 ms 95724 KB Output is correct
44 Correct 33 ms 1768 KB Output is correct
45 Correct 45 ms 1768 KB Output is correct
46 Correct 59 ms 1896 KB Output is correct
47 Correct 71 ms 2152 KB Output is correct
48 Correct 104 ms 3104 KB Output is correct
49 Correct 792 ms 64492 KB Output is correct
50 Correct 827 ms 64620 KB Output is correct
51 Correct 782 ms 65516 KB Output is correct
52 Correct 959 ms 64620 KB Output is correct
53 Correct 741 ms 64492 KB Output is correct
54 Correct 749 ms 64492 KB Output is correct
55 Correct 736 ms 64492 KB Output is correct
56 Correct 68 ms 2152 KB Output is correct
57 Correct 129 ms 2024 KB Output is correct
58 Correct 246 ms 2860 KB Output is correct
59 Correct 1127 ms 73580 KB Output is correct
60 Correct 1353 ms 73452 KB Output is correct
61 Correct 982 ms 73580 KB Output is correct
62 Correct 854 ms 77416 KB Output is correct
63 Correct 1270 ms 76012 KB Output is correct
64 Correct 1098 ms 74092 KB Output is correct
65 Correct 986 ms 73576 KB Output is correct
66 Correct 1124 ms 73708 KB Output is correct
67 Correct 1057 ms 78000 KB Output is correct
68 Correct 905 ms 87656 KB Output is correct
69 Correct 1422 ms 96756 KB Output is correct