# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
176088 |
2020-01-07T21:08:57 Z |
kishtarn555 |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
121820 KB |
#include "seats.h"
#include <iostream>
#include <algorithm>
using namespace std;
#define ind(a,b) ((a)*(WW+2)+b)
int mat[2000000];
vector<int> r;
vector<int> c;
int HH,WW;
struct st {
st *l, *r;
int m,f;
int M,F;
int lz1,lz2;
};
st *bl,*wt;
st* build (int l, int r) {
st * n = new st;
n->lz1=0;
n->lz2=0;
n->m=0;
n->f=1;
n->M=0;
n->F=1;
n->l=n->r=NULL;
if (l==r)
return n;
n->l = build(l, (l+r)/2);
n->r = build((l+r)/2+1,r);
n->f = n->l->f+ n->r->f;
n->F = n->l->F+ n->r->F;
return n;
}
int tmp[4];
void push(st *cur) {
cur->m+=cur->lz1;
cur->M+=cur->lz2;
if (cur->l) {
cur->l->lz1+=cur->lz1;
cur->l->lz2+=cur->lz2;
cur->r->lz1+=cur->lz1;
cur->r->lz2+=cur->lz2;
}
cur->lz1=0;
cur->lz2=0;
}
void update (st * cur, int l,int r, const int i,const int j,const int v1,const int v2) {
push(cur);
if (j < l || r < i)
return;
if (i<=l && r<=j) {
cur->lz1+=v1;
cur->lz2+=v2;
push(cur);
return;
}
int m =(l+r)/2;
update(cur->l, l,m, i,j,v1,v2);
update(cur->r, m+1,r, i,j,v1,v2);
if (cur->l->M < cur->r->M) {
cur->M=cur->l->M;
cur->F=cur->l->F;
cur->m=cur->l->m;
cur->f=cur->l->f;
}else if (cur->l->M > cur->r->M) {
cur->M=cur->r->M;
cur->F=cur->r->F;
cur->m=cur->r->m;
cur->f=cur->r->f;
}else {
if (cur->l->m < cur->r->m) {
cur->M=cur->l->M;
cur->F=cur->l->F;
cur->m=cur->l->m;
cur->f=cur->l->f;
} else if (cur->l->m > cur->r->m) {
cur->M=cur->r->M;
cur->F=cur->r->F;
cur->m=cur->r->m;
cur->f=cur->r->f;
} else {
cur->M=cur->r->M;
cur->F=cur->r->F+cur->l->F;
cur->m=cur->r->m;
cur->f=cur->r->f+cur->l->f;
}
}
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
HH=H;
WW=W;
r=R;
c=C;
for (int i =0; i < H+2; i++) {
for (int j =0; j< W+2; j++)
mat[ind(i,j)]=H*W;
}
for (int i =0; i < H*W; i++) {
mat[ ind(R[i]+1 ,C[i]+1)]=i;
}
bl=build(0,H*W-1);
for (int i =1; i < H+2; i++) {
for (int j =1; j < W+2; j++) {
tmp[0]=mat[ind(i-1,j-1)];
tmp[1]=mat[ind(i-1,j)];
tmp[2]=mat[ind(i,j-1)];
tmp[3]=mat[ind(i,j)];
sort(tmp,tmp+4);
// cout << mat[i][j]<<"::"<<tmp[0]<<","<<tmp[1]<<","<<tmp[2]<<","<<tmp[3]<<","<<tmp[4]<<endl;
int ind=2;
if (tmp[2]==H*W)ind=1;
if (tmp[1]==H*W)ind=0;
// cout << tmp[0]<<","<<tmp[1]-1<<";1 pintado"<<endl;
// if (ind==2)
update(bl, 0, H*W-1, tmp[0],tmp[1]-1,1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, H*W-1, tmp[ind],tmp[ind+1]-1,0,1);
}
}
}
// for (int i =0; i <)
// cout <<"{"<< bl->m <<","<<bl->f<<"}"<<"{"<<bl->M<<","<<bl->F <<"}";
// cout << endl;
// cout << endl;
}
int swap_seats(int a, int b) {
int r1=r[a]+1,c1=c[a]+1;
int r2=r[b]+1,c2=c[b]+1;
// cout <<"______________"<<endl;
// cout << r1 << ","<<c1<<endl;
// cout << r2 << ","<<c2<<endl;
swap(r[a],r[b]);
swap(c[a],c[b]);
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[ind(i+r1-1,j+c1-1)];
tmp[1]=mat[ind(i+r1-1,j+c1)];
tmp[2]=mat[ind(i+r1,j+c1-1)];
tmp[3]=mat[ind(i+r1,j+c1)];
sort(tmp,tmp+4);
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,-1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,-1);
}
}
}
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[ind(i+r2-1,j+c2-1)];
tmp[1]=mat[ind(i+r2-1,j+c2)];
tmp[2]=mat[ind(i+r2,j+c2-1)];
tmp[3]=mat[ind(i+r2,j+c2)];
sort(tmp,tmp+4);
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,-1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,-1);
}
}
}
swap(mat[ind(r1,c1)] ,mat[ind(r2,c2)]);
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[ind(i+r1-1,j+c1-1)];
tmp[1]=mat[ind(i+r1-1,j+c1)];
tmp[2]=mat[ind(i+r1,j+c1-1)];
tmp[3]=mat[ind(i+r1,j+c1)];
sort(tmp,tmp+4);
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,1);
}
}
}
for (int i =0; i < 2; i++){
for (int j = 0; j < 2; j++) {
tmp[0]=mat[ind(i+r2-1,j+c2-1)];
tmp[1]=mat[ind(i+r2-1,j+c2)];
tmp[2]=mat[ind(i+r2,j+c2-1)];
tmp[3]=mat[ind(i+r2,j+c2)];
sort(tmp,tmp+4);;
int ind=2;
if (tmp[2]==HH*WW)ind=1;
if (tmp[1]==HH*WW)ind=0;
update(bl, 0, HH*WW-1, tmp[0],tmp[1]-1,1,0);
if (ind == 2){
// cout << tmp[ind]<<","<<tmp[ind+1]-1<<";3 pintado"<<endl<<endl;
update(bl, 0, HH*WW-1, tmp[ind],tmp[ind+1]-1,0,1);
}
}
}
int t =0;
if (bl->M ==0 && bl->m == 4) {
t= bl->f;
}
return t;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
376 KB |
Output is correct |
2 |
Correct |
34 ms |
376 KB |
Output is correct |
3 |
Correct |
52 ms |
504 KB |
Output is correct |
4 |
Correct |
31 ms |
504 KB |
Output is correct |
5 |
Correct |
27 ms |
504 KB |
Output is correct |
6 |
Correct |
46 ms |
488 KB |
Output is correct |
7 |
Correct |
49 ms |
504 KB |
Output is correct |
8 |
Correct |
45 ms |
376 KB |
Output is correct |
9 |
Correct |
45 ms |
532 KB |
Output is correct |
10 |
Correct |
49 ms |
504 KB |
Output is correct |
11 |
Correct |
45 ms |
504 KB |
Output is correct |
12 |
Correct |
28 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
376 KB |
Output is correct |
2 |
Correct |
34 ms |
376 KB |
Output is correct |
3 |
Correct |
52 ms |
504 KB |
Output is correct |
4 |
Correct |
31 ms |
504 KB |
Output is correct |
5 |
Correct |
27 ms |
504 KB |
Output is correct |
6 |
Correct |
46 ms |
488 KB |
Output is correct |
7 |
Correct |
49 ms |
504 KB |
Output is correct |
8 |
Correct |
45 ms |
376 KB |
Output is correct |
9 |
Correct |
45 ms |
532 KB |
Output is correct |
10 |
Correct |
49 ms |
504 KB |
Output is correct |
11 |
Correct |
45 ms |
504 KB |
Output is correct |
12 |
Correct |
28 ms |
632 KB |
Output is correct |
13 |
Correct |
124 ms |
1528 KB |
Output is correct |
14 |
Correct |
151 ms |
1656 KB |
Output is correct |
15 |
Correct |
86 ms |
1704 KB |
Output is correct |
16 |
Correct |
63 ms |
1656 KB |
Output is correct |
17 |
Correct |
105 ms |
1656 KB |
Output is correct |
18 |
Correct |
103 ms |
1632 KB |
Output is correct |
19 |
Correct |
99 ms |
1656 KB |
Output is correct |
20 |
Correct |
83 ms |
1656 KB |
Output is correct |
21 |
Correct |
64 ms |
1656 KB |
Output is correct |
22 |
Correct |
65 ms |
1784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4030 ms |
121732 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
1688 KB |
Output is correct |
2 |
Correct |
305 ms |
11256 KB |
Output is correct |
3 |
Correct |
1919 ms |
121820 KB |
Output is correct |
4 |
Execution timed out |
4041 ms |
121692 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
1396 KB |
Output is correct |
2 |
Correct |
150 ms |
1548 KB |
Output is correct |
3 |
Correct |
263 ms |
1512 KB |
Output is correct |
4 |
Correct |
381 ms |
1676 KB |
Output is correct |
5 |
Correct |
651 ms |
2712 KB |
Output is correct |
6 |
Runtime error |
375 ms |
64732 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
376 KB |
Output is correct |
2 |
Correct |
34 ms |
376 KB |
Output is correct |
3 |
Correct |
52 ms |
504 KB |
Output is correct |
4 |
Correct |
31 ms |
504 KB |
Output is correct |
5 |
Correct |
27 ms |
504 KB |
Output is correct |
6 |
Correct |
46 ms |
488 KB |
Output is correct |
7 |
Correct |
49 ms |
504 KB |
Output is correct |
8 |
Correct |
45 ms |
376 KB |
Output is correct |
9 |
Correct |
45 ms |
532 KB |
Output is correct |
10 |
Correct |
49 ms |
504 KB |
Output is correct |
11 |
Correct |
45 ms |
504 KB |
Output is correct |
12 |
Correct |
28 ms |
632 KB |
Output is correct |
13 |
Correct |
124 ms |
1528 KB |
Output is correct |
14 |
Correct |
151 ms |
1656 KB |
Output is correct |
15 |
Correct |
86 ms |
1704 KB |
Output is correct |
16 |
Correct |
63 ms |
1656 KB |
Output is correct |
17 |
Correct |
105 ms |
1656 KB |
Output is correct |
18 |
Correct |
103 ms |
1632 KB |
Output is correct |
19 |
Correct |
99 ms |
1656 KB |
Output is correct |
20 |
Correct |
83 ms |
1656 KB |
Output is correct |
21 |
Correct |
64 ms |
1656 KB |
Output is correct |
22 |
Correct |
65 ms |
1784 KB |
Output is correct |
23 |
Execution timed out |
4030 ms |
121732 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |