# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
198127 |
2020-01-24T18:49:33 Z |
hank55663 |
Seats (IOI18_seats) |
C++14 |
|
2574 ms |
176608 KB |
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
node *l,*r;
int Min,Minnum;
int a,b;
int tag;
node(int _a,int _b):a(_a),b(_b),Min(0),Minnum(1),tag(0),l(NULL),r(NULL){
}
}*root;
int Min(node *n){
return n->Min+n->tag;
}
void pull(node *n){
if(Min(n->l)==Min(n->r)){
n->Min=Min(n->l);
n->Minnum=n->l->Minnum+n->r->Minnum;
}
else if(Min(n->l)>Min(n->r)){
n->Min=Min(n->r);
n->Minnum=n->r->Minnum;
}
else{
n->Min=Min(n->l);
n->Minnum=n->l->Minnum;
}
}
void push(node *n){
n->l->tag+=n->tag;
n->r->tag+=n->tag;
n->tag=0;
}
void build(node *n,int *a){
if(n->a==n->b){
n->Min=a[n->a];
return;
}
int mid=(n->a+n->b)/2;
n->l=new node(n->a,mid);
n->r=new node(mid+1,n->b);
build(n->l,a);
build(n->r,a);
pull(n);
}
void add(node *n,int l,int r,int k){
if(l>r)return;
// if(n==root){
// printf("%d %d %d\n",l,r,k);
// }
if(n->a>=l&&n->b<=r){
n->tag+=k;
return;
}
if(n->b<l||n->a>r)return;
push(n);
add(n->l,l,r,k);
add(n->r,l,r,k);
pull(n);
}
int query(node *n,int l,int r){
if(l>r)return 0;
if(n->a>=l&&n->b<=r){
// printf("%d %d %d %d %d\n",Min(n),n->a,n->b,n->tag,n->Min);
assert(Min(n)>=4);
if(Min(n)==4)return n->Minnum;
else return 0;
}
if(n->b<l||n->a>r)return 0;
push(n);
int x=query(n->l,l,r)+query(n->r,l,r);
pull(n);
return x;
}
#define pii pair<int,int>
#define x first
#define y second
#define pb push_back
#define mp make_pair
pii p[1000005];
vector<vector<int> > v;
int X[4]={0,0,1,1};
int Y[4]={0,1,0,1};
int len;
int a[1000005];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
v.resize(H+2,vector<int>(W+2,H*W));
for(int i = 0;i<H*W;i++){
//printf("%d %d %d %d\n",H,W,R[i]+1,C[i]+1);
p[i]=mp(R[i]+1,C[i]+1);
//printf("%d %d %d\n",v[R[i]+1][C[i]+1],R[i],C[i]);
// assert(v[R[i]+1][C[i]+1]==1e9);
v[R[i]+1][C[i]+1]=i;
}
len=H*W-1;
root= new node(0,H*W-1);
//build(root);
for(int i =0;i<=H;i++){
for(int j=0;j<=W;j++){
int tmp[4];
for(int k =0;k<4;k++){
tmp[k]=v[i+X[k]][j+Y[k]];
}
sort(tmp,tmp+4);
a[tmp[0]]++;
a[tmp[1]]--;
a[tmp[2]]++;
a[tmp[3]]--;
//add(root,tmp[0],tmp[1]-1,1);
//add(root,tmp[1],len,-1);
// add(root,tmp[2],tmp[3]-1,1);
// add(root,tmp[3],len,-1);
}
}
for(int i = 1;i<=H*W;i++)a[i]+=a[i-1];
build(root,a);
}
int swap_seats(int a, int b) {
// printf("%d %d\n",a,b);
for(int t=0;t<2;t++){
for(int i=p[a].x-1;i<=p[a].x;i++){
for(int j=p[a].y-1;j<=p[a].y;j++){
int tmp[4];
for(int k=0;k<4;k++){
tmp[k]=v[i+X[k]][j+Y[k]];
}
sort(tmp,tmp+4);
add(root,tmp[0],tmp[1]-1,-1);
// add(root,tmp[1],len,1);
add(root,tmp[2],tmp[3]-1,-1);
//add(root,tmp[3],len,1);
}
}
swap(a,b);
}
swap(p[a],p[b]);
v[p[a].x][p[a].y]=a;
v[p[b].x][p[b].y]=b;
for(int t=0;t<2;t++){
for(int i=p[a].x-1;i<=p[a].x;i++){
for(int j=p[a].y-1;j<=p[a].y;j++){
int tmp[4];
for(int k=0;k<4;k++){
tmp[k]=v[i+X[k]][j+Y[k]];
}
sort(tmp,tmp+4);
add(root,tmp[0],tmp[1]-1,1);
//add(root,tmp[1],len,-1);
add(root,tmp[2],tmp[3]-1,1);
//add(root,tmp[3],len,-1);
}
}
swap(a,b);
}
// printf("%d\n",query(root,0,len));
return query(root,0,len);
}
Compilation message
seats.cpp: In constructor 'node::node(int, int)':
seats.cpp:7:11: warning: 'node::b' will be initialized after [-Wreorder]
int a,b;
^
seats.cpp:6:9: warning: 'int node::Min' [-Wreorder]
int Min,Minnum;
^~~
seats.cpp:9:5: warning: when initialized here [-Wreorder]
node(int _a,int _b):a(_a),b(_b),Min(0),Minnum(1),tag(0),l(NULL),r(NULL){
^~~~
seats.cpp:8:9: warning: 'node::tag' will be initialized after [-Wreorder]
int tag;
^~~
seats.cpp:5:11: warning: 'node* node::l' [-Wreorder]
node *l,*r;
^
seats.cpp:9:5: warning: when initialized here [-Wreorder]
node(int _a,int _b):a(_a),b(_b),Min(0),Minnum(1),tag(0),l(NULL),r(NULL){
^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
504 KB |
Output is correct |
2 |
Correct |
25 ms |
504 KB |
Output is correct |
3 |
Correct |
39 ms |
504 KB |
Output is correct |
4 |
Correct |
24 ms |
504 KB |
Output is correct |
5 |
Correct |
21 ms |
508 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
504 KB |
Output is correct |
8 |
Correct |
32 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
504 KB |
Output is correct |
12 |
Correct |
22 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
504 KB |
Output is correct |
2 |
Correct |
25 ms |
504 KB |
Output is correct |
3 |
Correct |
39 ms |
504 KB |
Output is correct |
4 |
Correct |
24 ms |
504 KB |
Output is correct |
5 |
Correct |
21 ms |
508 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
504 KB |
Output is correct |
8 |
Correct |
32 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
504 KB |
Output is correct |
12 |
Correct |
22 ms |
504 KB |
Output is correct |
13 |
Correct |
82 ms |
1656 KB |
Output is correct |
14 |
Correct |
92 ms |
1656 KB |
Output is correct |
15 |
Correct |
49 ms |
1656 KB |
Output is correct |
16 |
Correct |
39 ms |
2168 KB |
Output is correct |
17 |
Correct |
63 ms |
1784 KB |
Output is correct |
18 |
Correct |
65 ms |
1604 KB |
Output is correct |
19 |
Correct |
61 ms |
1656 KB |
Output is correct |
20 |
Correct |
64 ms |
1932 KB |
Output is correct |
21 |
Correct |
40 ms |
1784 KB |
Output is correct |
22 |
Correct |
42 ms |
2168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
817 ms |
125712 KB |
Output is correct |
2 |
Correct |
630 ms |
125660 KB |
Output is correct |
3 |
Correct |
608 ms |
125816 KB |
Output is correct |
4 |
Correct |
599 ms |
125820 KB |
Output is correct |
5 |
Correct |
599 ms |
125688 KB |
Output is correct |
6 |
Correct |
655 ms |
125688 KB |
Output is correct |
7 |
Correct |
647 ms |
125732 KB |
Output is correct |
8 |
Correct |
620 ms |
125764 KB |
Output is correct |
9 |
Correct |
610 ms |
125720 KB |
Output is correct |
10 |
Correct |
600 ms |
125816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
1656 KB |
Output is correct |
2 |
Correct |
143 ms |
11740 KB |
Output is correct |
3 |
Correct |
589 ms |
125600 KB |
Output is correct |
4 |
Correct |
762 ms |
125680 KB |
Output is correct |
5 |
Correct |
581 ms |
133680 KB |
Output is correct |
6 |
Correct |
969 ms |
176608 KB |
Output is correct |
7 |
Correct |
591 ms |
128228 KB |
Output is correct |
8 |
Correct |
632 ms |
125708 KB |
Output is correct |
9 |
Correct |
619 ms |
126200 KB |
Output is correct |
10 |
Correct |
622 ms |
130452 KB |
Output is correct |
11 |
Correct |
622 ms |
149240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
1448 KB |
Output is correct |
2 |
Correct |
125 ms |
1708 KB |
Output is correct |
3 |
Correct |
195 ms |
1396 KB |
Output is correct |
4 |
Correct |
264 ms |
1664 KB |
Output is correct |
5 |
Correct |
424 ms |
2772 KB |
Output is correct |
6 |
Correct |
1172 ms |
133820 KB |
Output is correct |
7 |
Correct |
1229 ms |
133844 KB |
Output is correct |
8 |
Correct |
1178 ms |
133844 KB |
Output is correct |
9 |
Correct |
1518 ms |
133936 KB |
Output is correct |
10 |
Correct |
1064 ms |
150448 KB |
Output is correct |
11 |
Correct |
1066 ms |
150448 KB |
Output is correct |
12 |
Correct |
1048 ms |
150496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
504 KB |
Output is correct |
2 |
Correct |
25 ms |
504 KB |
Output is correct |
3 |
Correct |
39 ms |
504 KB |
Output is correct |
4 |
Correct |
24 ms |
504 KB |
Output is correct |
5 |
Correct |
21 ms |
508 KB |
Output is correct |
6 |
Correct |
33 ms |
504 KB |
Output is correct |
7 |
Correct |
35 ms |
504 KB |
Output is correct |
8 |
Correct |
32 ms |
504 KB |
Output is correct |
9 |
Correct |
33 ms |
504 KB |
Output is correct |
10 |
Correct |
36 ms |
504 KB |
Output is correct |
11 |
Correct |
32 ms |
504 KB |
Output is correct |
12 |
Correct |
22 ms |
504 KB |
Output is correct |
13 |
Correct |
82 ms |
1656 KB |
Output is correct |
14 |
Correct |
92 ms |
1656 KB |
Output is correct |
15 |
Correct |
49 ms |
1656 KB |
Output is correct |
16 |
Correct |
39 ms |
2168 KB |
Output is correct |
17 |
Correct |
63 ms |
1784 KB |
Output is correct |
18 |
Correct |
65 ms |
1604 KB |
Output is correct |
19 |
Correct |
61 ms |
1656 KB |
Output is correct |
20 |
Correct |
64 ms |
1932 KB |
Output is correct |
21 |
Correct |
40 ms |
1784 KB |
Output is correct |
22 |
Correct |
42 ms |
2168 KB |
Output is correct |
23 |
Correct |
817 ms |
125712 KB |
Output is correct |
24 |
Correct |
630 ms |
125660 KB |
Output is correct |
25 |
Correct |
608 ms |
125816 KB |
Output is correct |
26 |
Correct |
599 ms |
125820 KB |
Output is correct |
27 |
Correct |
599 ms |
125688 KB |
Output is correct |
28 |
Correct |
655 ms |
125688 KB |
Output is correct |
29 |
Correct |
647 ms |
125732 KB |
Output is correct |
30 |
Correct |
620 ms |
125764 KB |
Output is correct |
31 |
Correct |
610 ms |
125720 KB |
Output is correct |
32 |
Correct |
600 ms |
125816 KB |
Output is correct |
33 |
Correct |
80 ms |
1656 KB |
Output is correct |
34 |
Correct |
143 ms |
11740 KB |
Output is correct |
35 |
Correct |
589 ms |
125600 KB |
Output is correct |
36 |
Correct |
762 ms |
125680 KB |
Output is correct |
37 |
Correct |
581 ms |
133680 KB |
Output is correct |
38 |
Correct |
969 ms |
176608 KB |
Output is correct |
39 |
Correct |
591 ms |
128228 KB |
Output is correct |
40 |
Correct |
632 ms |
125708 KB |
Output is correct |
41 |
Correct |
619 ms |
126200 KB |
Output is correct |
42 |
Correct |
622 ms |
130452 KB |
Output is correct |
43 |
Correct |
622 ms |
149240 KB |
Output is correct |
44 |
Correct |
62 ms |
1448 KB |
Output is correct |
45 |
Correct |
125 ms |
1708 KB |
Output is correct |
46 |
Correct |
195 ms |
1396 KB |
Output is correct |
47 |
Correct |
264 ms |
1664 KB |
Output is correct |
48 |
Correct |
424 ms |
2772 KB |
Output is correct |
49 |
Correct |
1172 ms |
133820 KB |
Output is correct |
50 |
Correct |
1229 ms |
133844 KB |
Output is correct |
51 |
Correct |
1178 ms |
133844 KB |
Output is correct |
52 |
Correct |
1518 ms |
133936 KB |
Output is correct |
53 |
Correct |
1064 ms |
150448 KB |
Output is correct |
54 |
Correct |
1066 ms |
150448 KB |
Output is correct |
55 |
Correct |
1048 ms |
150496 KB |
Output is correct |
56 |
Correct |
151 ms |
2080 KB |
Output is correct |
57 |
Correct |
366 ms |
2076 KB |
Output is correct |
58 |
Correct |
619 ms |
3420 KB |
Output is correct |
59 |
Correct |
1774 ms |
142584 KB |
Output is correct |
60 |
Correct |
2574 ms |
142584 KB |
Output is correct |
61 |
Correct |
1449 ms |
142596 KB |
Output is correct |
62 |
Correct |
1225 ms |
146656 KB |
Output is correct |
63 |
Correct |
2193 ms |
145208 KB |
Output is correct |
64 |
Correct |
1612 ms |
143444 KB |
Output is correct |
65 |
Correct |
1462 ms |
142592 KB |
Output is correct |
66 |
Correct |
1917 ms |
142924 KB |
Output is correct |
67 |
Correct |
1635 ms |
147320 KB |
Output is correct |
68 |
Correct |
1302 ms |
156920 KB |
Output is correct |
69 |
Correct |
2169 ms |
166136 KB |
Output is correct |