# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
93527 |
2019-01-09T10:44:48 Z |
psmao |
Seats (IOI18_seats) |
C++14 |
|
2320 ms |
198264 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;
const int maxn = 1000050;
const int dx[] = {0,0,1,1};
const int dy[] = {1,0,0,1};
struct node{int l, r, cnt; pii v, tag;}t[maxn<<2];
int one[maxn], tri[maxn];
int h, w, r[maxn], c[maxn];
vector<vector<int> > A;
VI sur;
void build(int l, int r, int k)
{
t[k].l = l; t[k].r = r;
if(l == r)
{
t[k].v.fi = one[l];
t[k].v.se = tri[l];
t[k].tag = mp(0, 0);
t[k].cnt = 1;
return;
}
int mid = l + r >> 1;
build(l, mid, k<<1);
build(mid+1, r, k<<1|1);
t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}
void pd(int k)
{
t[k<<1].tag.fi += t[k].tag.fi;
t[k<<1].tag.se += t[k].tag.se;
t[k<<1].v.fi += t[k].tag.fi;
t[k<<1].v.se += t[k].tag.se;
t[k<<1|1].tag.fi += t[k].tag.fi;
t[k<<1|1].tag.se += t[k].tag.se;
t[k<<1|1].v.fi += t[k].tag.fi;
t[k<<1|1].v.se += t[k].tag.se;
t[k].tag = mp(0, 0);
}
void modify(int l, int r, pii x, int k)
{
if(l > r) return;
if(l <= t[k].l && t[k].r <= r)
{
t[k].v.fi += x.fi;
t[k].v.se += x.se;
t[k].tag.fi += x.fi;
t[k].tag.se += x.se;
return;
}
pd(k);
int mid = t[k].l + t[k].r >> 1;
if(r <= mid) modify(l, r, x, k<<1);
else if(l > mid) modify(l, r, x, k<<1|1);
else modify(l, mid, x, k<<1), modify(mid+1, r, x, k<<1|1);
t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}
void getx(int x, int y)
{
sur.clear();
fo(k,0,3) sur.pb(A[x+dx[k]][y+dy[k]]);
sort(sur.begin(), sur.end());
}
void update(int x, int y, int w)
{
getx(x, y);
modify(sur[0], sur[1]-1, mp(w, 0), 1);
modify(sur[2], sur[3]-1, mp(0, w), 1);
}
void upd(int x, int y, int val)
{
update(x, y-1, -1);
update(x-1, y, -1);
update(x, y, -1);
update(x-1, y-1, -1);
A[x][y] = val;
update(x, y-1, 1);
update(x-1, y, 1);
update(x, y, 1);
update(x-1, y-1, 1);
}
int ask()
{
return (t[1].v.fi == 4 && t[1].v.se == 0) ? t[1].cnt : 0;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
int n = R.size();
h = H; w = W;
fo(i,0,H+1)
{
vector<int> cur;
fo(j,0,W+1) cur.pb(H*W+1);
A.pb(cur);
cur.clear();
}
fo(i,0,n-1)
{
r[i+1] = R[i] + 1;
c[i+1] = C[i] + 1;
A[r[i+1]][c[i+1]] = i+1;
}
fo(i,0,H) fo(j,0,W)
{
getx(i, j);
++ one[sur[0]]; -- one[sur[1]];
++ tri[sur[2]]; -- tri[sur[3]];
}
fo(i,1,H*W) one[i] += one[i-1], tri[i] += tri[i-1];
build(1, H*W, 1);
}
int swap_seats(int a, int b)
{
++ a; ++ b;
int x = A[r[a]][c[a]], x2 = A[r[b]][c[b]];
swap(r[a], r[b]);
swap(c[a], c[b]);
upd(r[a], c[a], x);
upd(r[b], c[b], x2);
return ask();
}
Compilation message
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
seats.cpp: In function 'void modify(int, int, std::pair<int, int>, int)':
seats.cpp:83:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = t[k].l + t[k].r >> 1;
~~~~~~~^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
100 ms |
110200 KB |
Output is correct |
2 |
Correct |
109 ms |
110108 KB |
Output is correct |
3 |
Correct |
122 ms |
110072 KB |
Output is correct |
4 |
Correct |
107 ms |
110072 KB |
Output is correct |
5 |
Correct |
94 ms |
110272 KB |
Output is correct |
6 |
Correct |
104 ms |
110072 KB |
Output is correct |
7 |
Correct |
119 ms |
110048 KB |
Output is correct |
8 |
Correct |
118 ms |
110072 KB |
Output is correct |
9 |
Correct |
115 ms |
110072 KB |
Output is correct |
10 |
Correct |
119 ms |
110072 KB |
Output is correct |
11 |
Correct |
117 ms |
110248 KB |
Output is correct |
12 |
Correct |
104 ms |
110072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
100 ms |
110200 KB |
Output is correct |
2 |
Correct |
109 ms |
110108 KB |
Output is correct |
3 |
Correct |
122 ms |
110072 KB |
Output is correct |
4 |
Correct |
107 ms |
110072 KB |
Output is correct |
5 |
Correct |
94 ms |
110272 KB |
Output is correct |
6 |
Correct |
104 ms |
110072 KB |
Output is correct |
7 |
Correct |
119 ms |
110048 KB |
Output is correct |
8 |
Correct |
118 ms |
110072 KB |
Output is correct |
9 |
Correct |
115 ms |
110072 KB |
Output is correct |
10 |
Correct |
119 ms |
110072 KB |
Output is correct |
11 |
Correct |
117 ms |
110248 KB |
Output is correct |
12 |
Correct |
104 ms |
110072 KB |
Output is correct |
13 |
Correct |
166 ms |
110584 KB |
Output is correct |
14 |
Correct |
177 ms |
110696 KB |
Output is correct |
15 |
Correct |
132 ms |
110800 KB |
Output is correct |
16 |
Correct |
124 ms |
111028 KB |
Output is correct |
17 |
Correct |
147 ms |
110516 KB |
Output is correct |
18 |
Correct |
149 ms |
110520 KB |
Output is correct |
19 |
Correct |
148 ms |
110552 KB |
Output is correct |
20 |
Correct |
135 ms |
110912 KB |
Output is correct |
21 |
Correct |
121 ms |
110644 KB |
Output is correct |
22 |
Correct |
125 ms |
111156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
710 ms |
145400 KB |
Output is correct |
2 |
Correct |
541 ms |
145312 KB |
Output is correct |
3 |
Correct |
524 ms |
161444 KB |
Output is correct |
4 |
Correct |
524 ms |
161208 KB |
Output is correct |
5 |
Correct |
515 ms |
161272 KB |
Output is correct |
6 |
Correct |
515 ms |
161272 KB |
Output is correct |
7 |
Correct |
530 ms |
161400 KB |
Output is correct |
8 |
Correct |
550 ms |
161288 KB |
Output is correct |
9 |
Correct |
551 ms |
161272 KB |
Output is correct |
10 |
Correct |
517 ms |
161220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
110456 KB |
Output is correct |
2 |
Correct |
194 ms |
114140 KB |
Output is correct |
3 |
Correct |
478 ms |
146752 KB |
Output is correct |
4 |
Correct |
684 ms |
146992 KB |
Output is correct |
5 |
Correct |
478 ms |
159284 KB |
Output is correct |
6 |
Correct |
1027 ms |
198264 KB |
Output is correct |
7 |
Correct |
503 ms |
152496 KB |
Output is correct |
8 |
Correct |
541 ms |
148088 KB |
Output is correct |
9 |
Correct |
550 ms |
161588 KB |
Output is correct |
10 |
Correct |
550 ms |
165984 KB |
Output is correct |
11 |
Correct |
582 ms |
184700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
141 ms |
111604 KB |
Output is correct |
2 |
Correct |
198 ms |
111640 KB |
Output is correct |
3 |
Correct |
276 ms |
111820 KB |
Output is correct |
4 |
Correct |
361 ms |
111732 KB |
Output is correct |
5 |
Correct |
535 ms |
112308 KB |
Output is correct |
6 |
Correct |
1122 ms |
159892 KB |
Output is correct |
7 |
Correct |
1162 ms |
160148 KB |
Output is correct |
8 |
Correct |
1083 ms |
159892 KB |
Output is correct |
9 |
Correct |
1468 ms |
159764 KB |
Output is correct |
10 |
Correct |
1026 ms |
159764 KB |
Output is correct |
11 |
Correct |
1002 ms |
159760 KB |
Output is correct |
12 |
Correct |
959 ms |
159128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
100 ms |
110200 KB |
Output is correct |
2 |
Correct |
109 ms |
110108 KB |
Output is correct |
3 |
Correct |
122 ms |
110072 KB |
Output is correct |
4 |
Correct |
107 ms |
110072 KB |
Output is correct |
5 |
Correct |
94 ms |
110272 KB |
Output is correct |
6 |
Correct |
104 ms |
110072 KB |
Output is correct |
7 |
Correct |
119 ms |
110048 KB |
Output is correct |
8 |
Correct |
118 ms |
110072 KB |
Output is correct |
9 |
Correct |
115 ms |
110072 KB |
Output is correct |
10 |
Correct |
119 ms |
110072 KB |
Output is correct |
11 |
Correct |
117 ms |
110248 KB |
Output is correct |
12 |
Correct |
104 ms |
110072 KB |
Output is correct |
13 |
Correct |
166 ms |
110584 KB |
Output is correct |
14 |
Correct |
177 ms |
110696 KB |
Output is correct |
15 |
Correct |
132 ms |
110800 KB |
Output is correct |
16 |
Correct |
124 ms |
111028 KB |
Output is correct |
17 |
Correct |
147 ms |
110516 KB |
Output is correct |
18 |
Correct |
149 ms |
110520 KB |
Output is correct |
19 |
Correct |
148 ms |
110552 KB |
Output is correct |
20 |
Correct |
135 ms |
110912 KB |
Output is correct |
21 |
Correct |
121 ms |
110644 KB |
Output is correct |
22 |
Correct |
125 ms |
111156 KB |
Output is correct |
23 |
Correct |
710 ms |
145400 KB |
Output is correct |
24 |
Correct |
541 ms |
145312 KB |
Output is correct |
25 |
Correct |
524 ms |
161444 KB |
Output is correct |
26 |
Correct |
524 ms |
161208 KB |
Output is correct |
27 |
Correct |
515 ms |
161272 KB |
Output is correct |
28 |
Correct |
515 ms |
161272 KB |
Output is correct |
29 |
Correct |
530 ms |
161400 KB |
Output is correct |
30 |
Correct |
550 ms |
161288 KB |
Output is correct |
31 |
Correct |
551 ms |
161272 KB |
Output is correct |
32 |
Correct |
517 ms |
161220 KB |
Output is correct |
33 |
Correct |
169 ms |
110456 KB |
Output is correct |
34 |
Correct |
194 ms |
114140 KB |
Output is correct |
35 |
Correct |
478 ms |
146752 KB |
Output is correct |
36 |
Correct |
684 ms |
146992 KB |
Output is correct |
37 |
Correct |
478 ms |
159284 KB |
Output is correct |
38 |
Correct |
1027 ms |
198264 KB |
Output is correct |
39 |
Correct |
503 ms |
152496 KB |
Output is correct |
40 |
Correct |
541 ms |
148088 KB |
Output is correct |
41 |
Correct |
550 ms |
161588 KB |
Output is correct |
42 |
Correct |
550 ms |
165984 KB |
Output is correct |
43 |
Correct |
582 ms |
184700 KB |
Output is correct |
44 |
Correct |
141 ms |
111604 KB |
Output is correct |
45 |
Correct |
198 ms |
111640 KB |
Output is correct |
46 |
Correct |
276 ms |
111820 KB |
Output is correct |
47 |
Correct |
361 ms |
111732 KB |
Output is correct |
48 |
Correct |
535 ms |
112308 KB |
Output is correct |
49 |
Correct |
1122 ms |
159892 KB |
Output is correct |
50 |
Correct |
1162 ms |
160148 KB |
Output is correct |
51 |
Correct |
1083 ms |
159892 KB |
Output is correct |
52 |
Correct |
1468 ms |
159764 KB |
Output is correct |
53 |
Correct |
1026 ms |
159764 KB |
Output is correct |
54 |
Correct |
1002 ms |
159760 KB |
Output is correct |
55 |
Correct |
959 ms |
159128 KB |
Output is correct |
56 |
Correct |
213 ms |
111604 KB |
Output is correct |
57 |
Correct |
444 ms |
111708 KB |
Output is correct |
58 |
Correct |
757 ms |
112300 KB |
Output is correct |
59 |
Correct |
1658 ms |
162232 KB |
Output is correct |
60 |
Correct |
2320 ms |
162312 KB |
Output is correct |
61 |
Correct |
1459 ms |
162164 KB |
Output is correct |
62 |
Correct |
1190 ms |
168132 KB |
Output is correct |
63 |
Correct |
2097 ms |
166764 KB |
Output is correct |
64 |
Correct |
1616 ms |
163540 KB |
Output is correct |
65 |
Correct |
1440 ms |
162296 KB |
Output is correct |
66 |
Correct |
1715 ms |
162728 KB |
Output is correct |
67 |
Correct |
1651 ms |
166912 KB |
Output is correct |
68 |
Correct |
1332 ms |
176436 KB |
Output is correct |
69 |
Correct |
2113 ms |
185744 KB |
Output is correct |