# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
139702 |
2019-08-01T09:30:17 Z |
hamzqq9 |
Seats (IOI18_seats) |
C++14 |
|
3059 ms |
135836 KB |
#include "seats.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ll long long
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define orta ((ll)(bas+son)/2)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000000
#define N 1000005
#define MOD 998244353
using namespace std;
int h,w;
int ww[4][2]={1,1,-1,-1,-1,1,1,-1};
vector<vector<int>> a;
vector<int> r,c;
iii S[N*4];
ii lazy[N*4];
int eval() {
if(S[1].st.st==4 && S[1].st.nd==0) return S[1].nd;
return 0;
}
void shift(int node,ii lz) {
S[node].st.st+=lz.st;
S[node].st.nd+=lz.nd;
lazy[node].st+=lz.st;
lazy[node].nd+=lz.nd;
}
void push(int node) {
shift(node<<1,lazy[node]);
shift(node<<1|1,lazy[node]);
lazy[node]={0,0};
}
iii merge(iii a,iii b) {
if(a.st<b.st) return a;
if(b.st<a.st) return b;
return {a.st,a.nd+b.nd};
}
void up(int node,int bas,int son,int l,int r,ii lz) {
if(bas>r || son<l) return ;
if(bas>=l && son<=r) {
shift(node,lz);
return ;
}
push(node);
up(node<<1,bas,orta,l,r,lz);
up(node<<1|1,orta+1,son,l,r,lz);
S[node]=merge(S[node<<1],S[node<<1|1]);
}
void build(int node,int bas,int son) {
if(bas==son) {
S[node]={{0,0},1};
return ;
}
build(node<<1,bas,orta);
build(node<<1|1,orta+1,son);
S[node]=merge(S[node<<1],S[node<<1|1]);
}
int gtot(int xa,int ya,int xb,int yb) {
int tot=0;
if(xa>xb) swap(xa,xb);
if(ya>yb) swap(ya,yb);
for(int i=xa;i<=xb;i++) {
for(int j=ya;j<=yb;j++) {
tot+=(a[i][j]!=-1);
}
}
return tot;
}
void upd(int x,int y,int val,int sg) {
if(val==-1) return ;
int cnt[2][2]={0};
for(int i=0;i<4;i++) {
int tot=gtot(x+ww[i][0],y+ww[i][1],x,y);
if(tot==1) cnt[0][0]++;
if(tot==3) cnt[0][1]++;
}
a[x][y]=val;
for(int i=0;i<4;i++) {
int tot=gtot(x+ww[i][0],y+ww[i][1],x,y);
if(tot==1) cnt[1][0]++;
if(tot==3) cnt[1][1]++;
}
up(1,0,h*w-1,val,h*w-1,{sg*(cnt[1][0]-cnt[0][0]),sg*(cnt[1][1]-cnt[0][1])});
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
h=H;
w=W;
a=vector<vector<int>>(h+5,vector<int>(w+5,-1));
r=c=vector<int>(h*w+5);
build(1,0,h*w-1);
for(int i=0;i<h*w;i++) {
r[i]=R[i]+1;
c[i]=C[i]+1;
upd(r[i],c[i],i,1);
}
}
void upcr(int x,vector<pair<int,ii>>&cr) {
for(int i=r[x]-1;i<=r[x]+1;i++) {
for(int j=c[x]-1;j<=c[x]+1;j++) {
cr.pb({a[i][j],{i,j}});
}
}
}
void make_minus(vector<pair<int,ii>>& cr) {
for(auto x:cr) a[x.nd.st][x.nd.nd]=-1;
}
int swap_seats(int x, int y) {
#define iii pair<int,ii>
vector<iii> cr;
upcr(x,cr);
upcr(y,cr);
sort(cr.begin(),cr.end());
cr.erase(unique(cr.begin(),cr.end()),cr.end());
make_minus(cr);
for(auto x:cr) {
upd(x.nd.st,x.nd.nd,x.st,-1);
}
swap(r[x],r[y]);
swap(c[x],c[y]);
for(auto& x:cr) {
tie(x.nd.st,x.nd.nd)={r[x.st],c[x.st]};
}
make_minus(cr);
for(auto x:cr) {
upd(x.nd.st,x.nd.nd,x.st,1);
}
return eval();
}
Compilation message
seats.cpp:195:0: warning: "iii" redefined
#define iii pair<int,ii>
seats.cpp:8:0: note: this is the location of the previous definition
#define iii pair<ii,int>
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
504 KB |
Output is correct |
2 |
Correct |
41 ms |
500 KB |
Output is correct |
3 |
Correct |
58 ms |
504 KB |
Output is correct |
4 |
Correct |
27 ms |
624 KB |
Output is correct |
5 |
Correct |
26 ms |
508 KB |
Output is correct |
6 |
Correct |
46 ms |
540 KB |
Output is correct |
7 |
Correct |
51 ms |
500 KB |
Output is correct |
8 |
Correct |
54 ms |
504 KB |
Output is correct |
9 |
Correct |
54 ms |
508 KB |
Output is correct |
10 |
Correct |
51 ms |
504 KB |
Output is correct |
11 |
Correct |
45 ms |
504 KB |
Output is correct |
12 |
Correct |
26 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
504 KB |
Output is correct |
2 |
Correct |
41 ms |
500 KB |
Output is correct |
3 |
Correct |
58 ms |
504 KB |
Output is correct |
4 |
Correct |
27 ms |
624 KB |
Output is correct |
5 |
Correct |
26 ms |
508 KB |
Output is correct |
6 |
Correct |
46 ms |
540 KB |
Output is correct |
7 |
Correct |
51 ms |
500 KB |
Output is correct |
8 |
Correct |
54 ms |
504 KB |
Output is correct |
9 |
Correct |
54 ms |
508 KB |
Output is correct |
10 |
Correct |
51 ms |
504 KB |
Output is correct |
11 |
Correct |
45 ms |
504 KB |
Output is correct |
12 |
Correct |
26 ms |
504 KB |
Output is correct |
13 |
Correct |
115 ms |
1528 KB |
Output is correct |
14 |
Correct |
124 ms |
1504 KB |
Output is correct |
15 |
Correct |
54 ms |
1656 KB |
Output is correct |
16 |
Correct |
53 ms |
2168 KB |
Output is correct |
17 |
Correct |
91 ms |
1572 KB |
Output is correct |
18 |
Correct |
111 ms |
1532 KB |
Output is correct |
19 |
Correct |
108 ms |
1656 KB |
Output is correct |
20 |
Correct |
78 ms |
1784 KB |
Output is correct |
21 |
Correct |
54 ms |
1704 KB |
Output is correct |
22 |
Correct |
55 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1489 ms |
84864 KB |
Output is correct |
2 |
Correct |
1344 ms |
84996 KB |
Output is correct |
3 |
Correct |
1388 ms |
85056 KB |
Output is correct |
4 |
Correct |
1185 ms |
84804 KB |
Output is correct |
5 |
Correct |
1229 ms |
84976 KB |
Output is correct |
6 |
Correct |
1176 ms |
84968 KB |
Output is correct |
7 |
Correct |
1230 ms |
84956 KB |
Output is correct |
8 |
Correct |
1272 ms |
84984 KB |
Output is correct |
9 |
Correct |
1202 ms |
84984 KB |
Output is correct |
10 |
Correct |
1353 ms |
85112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
1528 KB |
Output is correct |
2 |
Correct |
234 ms |
9284 KB |
Output is correct |
3 |
Correct |
1191 ms |
84860 KB |
Output is correct |
4 |
Correct |
1386 ms |
84848 KB |
Output is correct |
5 |
Correct |
1136 ms |
104444 KB |
Output is correct |
6 |
Correct |
1477 ms |
135836 KB |
Output is correct |
7 |
Correct |
1236 ms |
91488 KB |
Output is correct |
8 |
Correct |
1212 ms |
85112 KB |
Output is correct |
9 |
Correct |
1282 ms |
85336 KB |
Output is correct |
10 |
Correct |
1253 ms |
91084 KB |
Output is correct |
11 |
Correct |
1179 ms |
116156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
2088 KB |
Output is correct |
2 |
Correct |
176 ms |
2048 KB |
Output is correct |
3 |
Correct |
249 ms |
2076 KB |
Output is correct |
4 |
Correct |
308 ms |
2144 KB |
Output is correct |
5 |
Correct |
411 ms |
3256 KB |
Output is correct |
6 |
Correct |
1713 ms |
105408 KB |
Output is correct |
7 |
Correct |
1753 ms |
105344 KB |
Output is correct |
8 |
Correct |
1660 ms |
105372 KB |
Output is correct |
9 |
Correct |
2019 ms |
105404 KB |
Output is correct |
10 |
Correct |
1596 ms |
105516 KB |
Output is correct |
11 |
Correct |
1602 ms |
105388 KB |
Output is correct |
12 |
Correct |
1594 ms |
105560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
504 KB |
Output is correct |
2 |
Correct |
41 ms |
500 KB |
Output is correct |
3 |
Correct |
58 ms |
504 KB |
Output is correct |
4 |
Correct |
27 ms |
624 KB |
Output is correct |
5 |
Correct |
26 ms |
508 KB |
Output is correct |
6 |
Correct |
46 ms |
540 KB |
Output is correct |
7 |
Correct |
51 ms |
500 KB |
Output is correct |
8 |
Correct |
54 ms |
504 KB |
Output is correct |
9 |
Correct |
54 ms |
508 KB |
Output is correct |
10 |
Correct |
51 ms |
504 KB |
Output is correct |
11 |
Correct |
45 ms |
504 KB |
Output is correct |
12 |
Correct |
26 ms |
504 KB |
Output is correct |
13 |
Correct |
115 ms |
1528 KB |
Output is correct |
14 |
Correct |
124 ms |
1504 KB |
Output is correct |
15 |
Correct |
54 ms |
1656 KB |
Output is correct |
16 |
Correct |
53 ms |
2168 KB |
Output is correct |
17 |
Correct |
91 ms |
1572 KB |
Output is correct |
18 |
Correct |
111 ms |
1532 KB |
Output is correct |
19 |
Correct |
108 ms |
1656 KB |
Output is correct |
20 |
Correct |
78 ms |
1784 KB |
Output is correct |
21 |
Correct |
54 ms |
1704 KB |
Output is correct |
22 |
Correct |
55 ms |
2040 KB |
Output is correct |
23 |
Correct |
1489 ms |
84864 KB |
Output is correct |
24 |
Correct |
1344 ms |
84996 KB |
Output is correct |
25 |
Correct |
1388 ms |
85056 KB |
Output is correct |
26 |
Correct |
1185 ms |
84804 KB |
Output is correct |
27 |
Correct |
1229 ms |
84976 KB |
Output is correct |
28 |
Correct |
1176 ms |
84968 KB |
Output is correct |
29 |
Correct |
1230 ms |
84956 KB |
Output is correct |
30 |
Correct |
1272 ms |
84984 KB |
Output is correct |
31 |
Correct |
1202 ms |
84984 KB |
Output is correct |
32 |
Correct |
1353 ms |
85112 KB |
Output is correct |
33 |
Correct |
113 ms |
1528 KB |
Output is correct |
34 |
Correct |
234 ms |
9284 KB |
Output is correct |
35 |
Correct |
1191 ms |
84860 KB |
Output is correct |
36 |
Correct |
1386 ms |
84848 KB |
Output is correct |
37 |
Correct |
1136 ms |
104444 KB |
Output is correct |
38 |
Correct |
1477 ms |
135836 KB |
Output is correct |
39 |
Correct |
1236 ms |
91488 KB |
Output is correct |
40 |
Correct |
1212 ms |
85112 KB |
Output is correct |
41 |
Correct |
1282 ms |
85336 KB |
Output is correct |
42 |
Correct |
1253 ms |
91084 KB |
Output is correct |
43 |
Correct |
1179 ms |
116156 KB |
Output is correct |
44 |
Correct |
117 ms |
2088 KB |
Output is correct |
45 |
Correct |
176 ms |
2048 KB |
Output is correct |
46 |
Correct |
249 ms |
2076 KB |
Output is correct |
47 |
Correct |
308 ms |
2144 KB |
Output is correct |
48 |
Correct |
411 ms |
3256 KB |
Output is correct |
49 |
Correct |
1713 ms |
105408 KB |
Output is correct |
50 |
Correct |
1753 ms |
105344 KB |
Output is correct |
51 |
Correct |
1660 ms |
105372 KB |
Output is correct |
52 |
Correct |
2019 ms |
105404 KB |
Output is correct |
53 |
Correct |
1596 ms |
105516 KB |
Output is correct |
54 |
Correct |
1602 ms |
105388 KB |
Output is correct |
55 |
Correct |
1594 ms |
105560 KB |
Output is correct |
56 |
Correct |
237 ms |
2028 KB |
Output is correct |
57 |
Correct |
577 ms |
2296 KB |
Output is correct |
58 |
Correct |
1055 ms |
3224 KB |
Output is correct |
59 |
Correct |
2777 ms |
85880 KB |
Output is correct |
60 |
Correct |
3059 ms |
86008 KB |
Output is correct |
61 |
Correct |
2524 ms |
85844 KB |
Output is correct |
62 |
Correct |
2066 ms |
95632 KB |
Output is correct |
63 |
Correct |
2804 ms |
92328 KB |
Output is correct |
64 |
Correct |
2759 ms |
87784 KB |
Output is correct |
65 |
Correct |
2588 ms |
86040 KB |
Output is correct |
66 |
Correct |
2872 ms |
86284 KB |
Output is correct |
67 |
Correct |
2718 ms |
91920 KB |
Output is correct |
68 |
Correct |
2254 ms |
105472 KB |
Output is correct |
69 |
Correct |
2701 ms |
117052 KB |
Output is correct |