# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
328600 |
2020-11-17T10:02:00 Z |
figter001 |
Seats (IOI18_seats) |
C++17 |
|
3379 ms |
193796 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
vector<vector<int>> loc,d;
vector<pair<int,int>> at;
const vector<pair<int,int>> dir = {{0,0},{0,1},{1,0},{1,1}};
const vector<vector<int>> X = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
struct node{
node *l,*r;
int lazy,mn,cnt;
node(){
l = r = NULL;
mn = 1e9;
lazy = 0;
cnt = 1;
}
void pro(){
mn += lazy;
if(l != NULL)l->lazy += lazy;
if(r != NULL)r->lazy += lazy;
lazy = 0;
}
void marge(){
if(l->mn < r->mn){
mn = l->mn;
cnt = l->cnt;
}else if(r->mn < l->mn){
mn = r->mn;
cnt = r->cnt;
}else if(l->mn == r->mn){
mn = l->mn;
cnt = l->cnt + r->cnt;
}
}
};
int n;
node *head;
void update(int at,int val,node *&n = head,int s = 1,int e = ::n){
if(n == NULL)n = new node();
if(s > at || e < at)return;
if(s == e){
n->mn = val;
n->cnt = 1;
return;
}
update(at , val , n->l , s , (s+e)/2);
update(at , val , n->r , (s+e)/2+1 , e);
n->marge();
// cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n';
}
void update_range(int l,int r,int val,node *&n = head,int s = 1,int e = ::n){
n->pro();
if(s > r || e < l || l > r)return;
if(s >= l && e <= r){
n->lazy += val;
n->pro();
return;
}
update_range(l , r , val , n->l , s , (s+e)/2);
update_range(l , r , val , n->r , (s+e)/2+1 , e);
n->marge();
// cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n';
}
/*
pair<int,int> get(int l,int r,node *& n = head,int s = 1,int e = ::n){
n->pro();
if(n == NULL)return {1e9,0};
if(s > r || e < l || l > r)return {1e9,0};
if(s >= l && e <= r)return {n->mn,n->cnt};
pair<int,int> a = get(l , r , n->l , s , (s+e) / 2);
pair<int,int> b = get(l , r , n->r , (s+e)/2+1 , e);
if(a.first < b.first)return a;
else if(a.first > b.first)return b;
else{
return {a.first , a.second + b.second};
}
}
*/
int h,w;
bool good(int i,int j){
if(i < 0 || j < 0 || i >= h || j >= w)return false;
return true;
}
int getd(int i,int j,int x){
if(!good(i,j) || loc[i][j] > x)return 0;
return 1;
}
int getv(int a){
return d[a][2] - d[a][3] + d[a][0] - d[a][1];
}
void add(int l,int r,int v){
update_range(l,r,v);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
bool v = false;
if(H > W){
v = true;
swap(H,W);
}
h = H;w = W;
n = H*W;
at = vector<pair<int,int>>(n);
d.resize(n,vector<int>(4));
loc.resize(H,vector<int>(W));
head = new node();
for(int i=0;i<n;i++){
if(v)swap(R[i],C[i]);
at[i] = {R[i] , C[i]};
loc[R[i]][C[i]] = i;
}
int sum = 0;
for(int i=0;i<n;i++){
for(int j=0;j<4;j++){
int x = at[i].first + dir[j].first;
int y = at[i].second + dir[j].second;
int w = getd(x-1,y-1,i) + getd(x-1,y,i) + getd(x,y-1,i) + getd(x,y,i);
d[i][w-1]++;
}
sum += getv(i);
// cerr << sum << '\n';
// cerr << i << " : ";
// for(int j=1;j<=4;j++){
// cerr << d[i][j] << ' ';
// }
// cerr << '\n';
update(i + 1 , sum);
}
// cerr << head->mn << ' ' << head->cnt << '\n';
// cerr << '\n';
return;
}
int swap_seats(int a, int b) {
swap(at[a] , at[b]);
swap(loc[at[a].first][at[a].second] , loc[at[b].first][at[b].second]);
int A = a,B = b;
// cerr << "MN : " << get(1,n).first << ' ' << get(1,n).second << '\n';
for(vector<int> i : X){
// cerr << a << ' ' << b << '\n';
int ai = at[A].first + i[0];
int aj = at[A].second + i[1];
if(good(ai,aj)){
int a = loc[ai][aj];
add(a+1 , n , -getv(a));
// cerr << "A : " << a << '\n';
// cerr << getv(a) << ' ';
d[a] = {0,0,0,0};
for(int j=0;j<4;j++){
int x = ai + dir[j].first;
int y = aj + dir[j].second;
int w = getd(x-1,y-1,a) + getd(x-1,y,a) + getd(x,y-1,a) + getd(x,y,a);
d[a][w-1]++;
}
add(a+1 , n , getv(a));
// cerr << getv(a) << '\n';
// for(int j=1;j<=4;j++)
// cerr << d[a][j] << ' ';
// cerr << '\n';
}
int bi = at[B].first + i[0];
int bj = at[B].second + i[1];
if(good(bi,bj)){
int b = loc[bi][bj];
add(b+1 , n , -getv(b));
// cerr << "B : " << b << '\n';
// cerr << getv(b) << ' ';
d[b] = {0,0,0,0};
for(int j=0;j<4;j++){
int x = bi + dir[j].first;
int y = bj + dir[j].second;
int w = getd(x-1,y-1,b) + getd(x-1,y,b) + getd(x,y-1,b) + getd(x,y,b);
d[b][w-1]++;
}
add(b+1 , n , getv(b));
// cerr << getv(b) << '\n';
// for(int j=1;j<=4;j++)
// cerr << d[b][j] << ' ';
// cerr << '\n';
}
// cerr << "WTF : " << get(1,n-1).first << ' ' << get(1,n-1).second << '\n';
// cerr << "mn : " << get(1,n).first << ' ' << get(1,n).second << '\n';
}
// cerr << head->mn << ' ' << head->cnt << '\n';
// cerr << get(n,n).first << '\n';
return head->cnt;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
492 KB |
Output is correct |
2 |
Correct |
27 ms |
492 KB |
Output is correct |
3 |
Correct |
37 ms |
492 KB |
Output is correct |
4 |
Correct |
16 ms |
492 KB |
Output is correct |
5 |
Correct |
17 ms |
396 KB |
Output is correct |
6 |
Correct |
29 ms |
492 KB |
Output is correct |
7 |
Correct |
33 ms |
492 KB |
Output is correct |
8 |
Correct |
36 ms |
492 KB |
Output is correct |
9 |
Correct |
36 ms |
492 KB |
Output is correct |
10 |
Correct |
33 ms |
492 KB |
Output is correct |
11 |
Correct |
29 ms |
560 KB |
Output is correct |
12 |
Correct |
15 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
492 KB |
Output is correct |
2 |
Correct |
27 ms |
492 KB |
Output is correct |
3 |
Correct |
37 ms |
492 KB |
Output is correct |
4 |
Correct |
16 ms |
492 KB |
Output is correct |
5 |
Correct |
17 ms |
396 KB |
Output is correct |
6 |
Correct |
29 ms |
492 KB |
Output is correct |
7 |
Correct |
33 ms |
492 KB |
Output is correct |
8 |
Correct |
36 ms |
492 KB |
Output is correct |
9 |
Correct |
36 ms |
492 KB |
Output is correct |
10 |
Correct |
33 ms |
492 KB |
Output is correct |
11 |
Correct |
29 ms |
560 KB |
Output is correct |
12 |
Correct |
15 ms |
492 KB |
Output is correct |
13 |
Correct |
91 ms |
2284 KB |
Output is correct |
14 |
Correct |
95 ms |
2156 KB |
Output is correct |
15 |
Correct |
39 ms |
2156 KB |
Output is correct |
16 |
Correct |
35 ms |
2156 KB |
Output is correct |
17 |
Correct |
77 ms |
2156 KB |
Output is correct |
18 |
Correct |
84 ms |
2156 KB |
Output is correct |
19 |
Correct |
84 ms |
2284 KB |
Output is correct |
20 |
Correct |
60 ms |
2156 KB |
Output is correct |
21 |
Correct |
35 ms |
2156 KB |
Output is correct |
22 |
Correct |
36 ms |
2156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1280 ms |
176640 KB |
Output is correct |
2 |
Correct |
1076 ms |
176620 KB |
Output is correct |
3 |
Correct |
1062 ms |
176492 KB |
Output is correct |
4 |
Correct |
1077 ms |
176748 KB |
Output is correct |
5 |
Correct |
1076 ms |
176780 KB |
Output is correct |
6 |
Correct |
1035 ms |
176492 KB |
Output is correct |
7 |
Correct |
1052 ms |
176620 KB |
Output is correct |
8 |
Correct |
1085 ms |
176488 KB |
Output is correct |
9 |
Correct |
1064 ms |
176620 KB |
Output is correct |
10 |
Correct |
1053 ms |
176620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
2156 KB |
Output is correct |
2 |
Correct |
199 ms |
16236 KB |
Output is correct |
3 |
Correct |
1044 ms |
176604 KB |
Output is correct |
4 |
Correct |
1263 ms |
176492 KB |
Output is correct |
5 |
Correct |
926 ms |
176504 KB |
Output is correct |
6 |
Correct |
1080 ms |
176548 KB |
Output is correct |
7 |
Correct |
1025 ms |
192624 KB |
Output is correct |
8 |
Correct |
1087 ms |
192492 KB |
Output is correct |
9 |
Correct |
1075 ms |
192492 KB |
Output is correct |
10 |
Correct |
1072 ms |
192484 KB |
Output is correct |
11 |
Correct |
1006 ms |
192584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
1384 KB |
Output is correct |
2 |
Correct |
95 ms |
1328 KB |
Output is correct |
3 |
Correct |
152 ms |
1384 KB |
Output is correct |
4 |
Correct |
211 ms |
1692 KB |
Output is correct |
5 |
Correct |
310 ms |
3268 KB |
Output is correct |
6 |
Correct |
1475 ms |
176932 KB |
Output is correct |
7 |
Correct |
1513 ms |
176804 KB |
Output is correct |
8 |
Correct |
1474 ms |
176832 KB |
Output is correct |
9 |
Correct |
1751 ms |
177060 KB |
Output is correct |
10 |
Correct |
1364 ms |
177060 KB |
Output is correct |
11 |
Correct |
1363 ms |
177060 KB |
Output is correct |
12 |
Correct |
1336 ms |
176804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
492 KB |
Output is correct |
2 |
Correct |
27 ms |
492 KB |
Output is correct |
3 |
Correct |
37 ms |
492 KB |
Output is correct |
4 |
Correct |
16 ms |
492 KB |
Output is correct |
5 |
Correct |
17 ms |
396 KB |
Output is correct |
6 |
Correct |
29 ms |
492 KB |
Output is correct |
7 |
Correct |
33 ms |
492 KB |
Output is correct |
8 |
Correct |
36 ms |
492 KB |
Output is correct |
9 |
Correct |
36 ms |
492 KB |
Output is correct |
10 |
Correct |
33 ms |
492 KB |
Output is correct |
11 |
Correct |
29 ms |
560 KB |
Output is correct |
12 |
Correct |
15 ms |
492 KB |
Output is correct |
13 |
Correct |
91 ms |
2284 KB |
Output is correct |
14 |
Correct |
95 ms |
2156 KB |
Output is correct |
15 |
Correct |
39 ms |
2156 KB |
Output is correct |
16 |
Correct |
35 ms |
2156 KB |
Output is correct |
17 |
Correct |
77 ms |
2156 KB |
Output is correct |
18 |
Correct |
84 ms |
2156 KB |
Output is correct |
19 |
Correct |
84 ms |
2284 KB |
Output is correct |
20 |
Correct |
60 ms |
2156 KB |
Output is correct |
21 |
Correct |
35 ms |
2156 KB |
Output is correct |
22 |
Correct |
36 ms |
2156 KB |
Output is correct |
23 |
Correct |
1280 ms |
176640 KB |
Output is correct |
24 |
Correct |
1076 ms |
176620 KB |
Output is correct |
25 |
Correct |
1062 ms |
176492 KB |
Output is correct |
26 |
Correct |
1077 ms |
176748 KB |
Output is correct |
27 |
Correct |
1076 ms |
176780 KB |
Output is correct |
28 |
Correct |
1035 ms |
176492 KB |
Output is correct |
29 |
Correct |
1052 ms |
176620 KB |
Output is correct |
30 |
Correct |
1085 ms |
176488 KB |
Output is correct |
31 |
Correct |
1064 ms |
176620 KB |
Output is correct |
32 |
Correct |
1053 ms |
176620 KB |
Output is correct |
33 |
Correct |
89 ms |
2156 KB |
Output is correct |
34 |
Correct |
199 ms |
16236 KB |
Output is correct |
35 |
Correct |
1044 ms |
176604 KB |
Output is correct |
36 |
Correct |
1263 ms |
176492 KB |
Output is correct |
37 |
Correct |
926 ms |
176504 KB |
Output is correct |
38 |
Correct |
1080 ms |
176548 KB |
Output is correct |
39 |
Correct |
1025 ms |
192624 KB |
Output is correct |
40 |
Correct |
1087 ms |
192492 KB |
Output is correct |
41 |
Correct |
1075 ms |
192492 KB |
Output is correct |
42 |
Correct |
1072 ms |
192484 KB |
Output is correct |
43 |
Correct |
1006 ms |
192584 KB |
Output is correct |
44 |
Correct |
67 ms |
1384 KB |
Output is correct |
45 |
Correct |
95 ms |
1328 KB |
Output is correct |
46 |
Correct |
152 ms |
1384 KB |
Output is correct |
47 |
Correct |
211 ms |
1692 KB |
Output is correct |
48 |
Correct |
310 ms |
3268 KB |
Output is correct |
49 |
Correct |
1475 ms |
176932 KB |
Output is correct |
50 |
Correct |
1513 ms |
176804 KB |
Output is correct |
51 |
Correct |
1474 ms |
176832 KB |
Output is correct |
52 |
Correct |
1751 ms |
177060 KB |
Output is correct |
53 |
Correct |
1364 ms |
177060 KB |
Output is correct |
54 |
Correct |
1363 ms |
177060 KB |
Output is correct |
55 |
Correct |
1336 ms |
176804 KB |
Output is correct |
56 |
Correct |
159 ms |
2024 KB |
Output is correct |
57 |
Correct |
371 ms |
2024 KB |
Output is correct |
58 |
Correct |
803 ms |
4140 KB |
Output is correct |
59 |
Correct |
2615 ms |
193644 KB |
Output is correct |
60 |
Correct |
3379 ms |
193492 KB |
Output is correct |
61 |
Correct |
2271 ms |
193796 KB |
Output is correct |
62 |
Correct |
1810 ms |
193524 KB |
Output is correct |
63 |
Correct |
2848 ms |
193620 KB |
Output is correct |
64 |
Correct |
2418 ms |
193636 KB |
Output is correct |
65 |
Correct |
2275 ms |
193388 KB |
Output is correct |
66 |
Correct |
2599 ms |
193560 KB |
Output is correct |
67 |
Correct |
2405 ms |
193508 KB |
Output is correct |
68 |
Correct |
1943 ms |
193660 KB |
Output is correct |
69 |
Correct |
2586 ms |
193736 KB |
Output is correct |