# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
80812 |
2018-10-22T12:07:20 Z |
Bodo171 |
Seats (IOI18_seats) |
C++14 |
|
3232 ms |
233352 KB |
#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int nmax=1000*1000+5;
int d1[]={-1,0,1,0};
int d2[]={0,-1,0,1};
struct node
{
int mn,upd,cnt;
}arb[4*nmax];
vector<int> a[nmax],viz[nmax];
vector<int> r,c;
int v[10],L[15],C[15];
int st,dr,n,h,w,lf,cf,i,j,nr;
void update(int nod,int l,int r,int st,int dr,int value)
{
if(st<=l&&r<=dr)
{
arb[nod].upd+=value;
return;
}
int m=(l+r)/2;
if(arb[nod].upd)
{
update(2*nod,l,m,l,m,arb[nod].upd);
update(2*nod+1,m+1,r,m+1,r,arb[nod].upd);
arb[nod].upd=0;
}
if(st<=m) update(2*nod,l,m,st,dr,value);
if(m<dr) update(2*nod+1,m+1,r,st,dr,value);
arb[nod].mn=min(arb[2*nod].mn+arb[2*nod].upd,arb[2*nod+1].mn+arb[2*nod+1].upd);
arb[nod].cnt=0;
if(arb[nod].mn==arb[2*nod].mn+arb[2*nod].upd)
arb[nod].cnt+=arb[2*nod].cnt;
if(arb[nod].mn==arb[2*nod+1].mn+arb[2*nod+1].upd)
arb[nod].cnt+=arb[2*nod+1].cnt;
}
void build(int nod,int l,int r)
{
if(l==r)
{
arb[nod].cnt=1;
return;
}
int m=(l+r)/2;
build(2*nod,l,m);
build(2*nod+1,m+1,r);
arb[nod].cnt=arb[2*nod].cnt+arb[2*nod+1].cnt;
}
void upd(int l,int c,int cat)
{
st=a[l][c];dr=min(a[l-1][c],a[l][c-1])-1;//facem update pt colt
if(st<=dr)
update(1,1,n,st,dr,cat);
//facem update pt celule din afara
for(int idx=0;idx<4;idx++)
{
lf=l+d1[idx];cf=c+d2[idx];
v[idx]=a[lf][cf];
}
sort(v,v+4);
st=v[1];dr=a[l][c]-1;
if(st<=dr)
update(1,1,n,st,dr,cat);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
r=R;c=C;
for(i=0;i<=H+1;i++)
for(j=1;j<=W+3;j++)
a[i].push_back(n+1),viz[i].push_back(0);
for(i=0;i<r.size();i++)
{
r[i]++;c[i]++;
a[r[i]][c[i]]=i+1;
}
h=H,w=W;
n=h*w;
build(1,1,n);
for(i=0;i<=h+1;i++)
a[i][0]=a[i][w+1]=n+1;
for(i=0;i<=w+1;i++)
a[0][i]=a[h+1][i]=n+1;
for(i=1;i<=h;i++)
for(j=1;j<=w;j++)
{
upd(i,j,1);
}
}
void rupe_tot(int ll,int cc)
{
if(!viz[ll][cc])
{
viz[ll][cc]=1;
++nr;
L[nr]=ll;C[nr]=cc;
}
for(int idx=0;idx<4;idx++)
{
lf=ll+d1[idx];cf=cc+d2[idx];
if((!viz[lf][cf])&&lf>=1&&cf>=1&&lf<=h&&cf<=w)
{
viz[lf][cf]=1;
++nr;
L[nr]=lf;C[nr]=cf;
}
}
}
int swap_seats(int aa, int b) {
nr=0;
rupe_tot(r[aa],c[aa]);
rupe_tot(r[b],c[b]);
for(int i=1;i<=nr;i++)
upd(L[i],C[i],-1);
swap(a[r[aa]][c[aa]],a[r[b]][c[b]]);
swap(r[aa],r[b]);swap(c[aa],c[b]);
for(int i=1;i<=nr;i++)
upd(L[i],C[i],1),viz[L[i]][C[i]]=0;
if(arb[1].mn+arb[1].upd==1) return arb[1].cnt;
return 0;
}
Compilation message
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<r.size();i++)
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
47608 KB |
Output is correct |
2 |
Correct |
64 ms |
47608 KB |
Output is correct |
3 |
Correct |
76 ms |
47632 KB |
Output is correct |
4 |
Correct |
63 ms |
47728 KB |
Output is correct |
5 |
Correct |
63 ms |
47824 KB |
Output is correct |
6 |
Correct |
72 ms |
47848 KB |
Output is correct |
7 |
Correct |
87 ms |
47980 KB |
Output is correct |
8 |
Correct |
73 ms |
47980 KB |
Output is correct |
9 |
Correct |
67 ms |
47980 KB |
Output is correct |
10 |
Correct |
76 ms |
48008 KB |
Output is correct |
11 |
Correct |
70 ms |
48068 KB |
Output is correct |
12 |
Correct |
75 ms |
48072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
47608 KB |
Output is correct |
2 |
Correct |
64 ms |
47608 KB |
Output is correct |
3 |
Correct |
76 ms |
47632 KB |
Output is correct |
4 |
Correct |
63 ms |
47728 KB |
Output is correct |
5 |
Correct |
63 ms |
47824 KB |
Output is correct |
6 |
Correct |
72 ms |
47848 KB |
Output is correct |
7 |
Correct |
87 ms |
47980 KB |
Output is correct |
8 |
Correct |
73 ms |
47980 KB |
Output is correct |
9 |
Correct |
67 ms |
47980 KB |
Output is correct |
10 |
Correct |
76 ms |
48008 KB |
Output is correct |
11 |
Correct |
70 ms |
48068 KB |
Output is correct |
12 |
Correct |
75 ms |
48072 KB |
Output is correct |
13 |
Correct |
105 ms |
48928 KB |
Output is correct |
14 |
Correct |
119 ms |
48932 KB |
Output is correct |
15 |
Correct |
88 ms |
49084 KB |
Output is correct |
16 |
Correct |
68 ms |
49492 KB |
Output is correct |
17 |
Correct |
98 ms |
49492 KB |
Output is correct |
18 |
Correct |
88 ms |
49492 KB |
Output is correct |
19 |
Correct |
84 ms |
49492 KB |
Output is correct |
20 |
Correct |
86 ms |
49664 KB |
Output is correct |
21 |
Correct |
77 ms |
49716 KB |
Output is correct |
22 |
Correct |
75 ms |
50288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1936 ms |
110756 KB |
Output is correct |
2 |
Correct |
935 ms |
125980 KB |
Output is correct |
3 |
Correct |
976 ms |
140572 KB |
Output is correct |
4 |
Correct |
633 ms |
140640 KB |
Output is correct |
5 |
Correct |
798 ms |
155600 KB |
Output is correct |
6 |
Correct |
1043 ms |
166928 KB |
Output is correct |
7 |
Correct |
1002 ms |
166928 KB |
Output is correct |
8 |
Correct |
904 ms |
167040 KB |
Output is correct |
9 |
Correct |
936 ms |
167040 KB |
Output is correct |
10 |
Correct |
749 ms |
167040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
167040 KB |
Output is correct |
2 |
Correct |
173 ms |
167040 KB |
Output is correct |
3 |
Correct |
836 ms |
167040 KB |
Output is correct |
4 |
Correct |
1879 ms |
167040 KB |
Output is correct |
5 |
Correct |
747 ms |
182560 KB |
Output is correct |
6 |
Correct |
2188 ms |
221440 KB |
Output is correct |
7 |
Correct |
717 ms |
221440 KB |
Output is correct |
8 |
Correct |
1130 ms |
221440 KB |
Output is correct |
9 |
Correct |
893 ms |
221440 KB |
Output is correct |
10 |
Correct |
856 ms |
221440 KB |
Output is correct |
11 |
Correct |
934 ms |
221440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
221440 KB |
Output is correct |
2 |
Correct |
130 ms |
221440 KB |
Output is correct |
3 |
Correct |
193 ms |
221440 KB |
Output is correct |
4 |
Correct |
223 ms |
221440 KB |
Output is correct |
5 |
Correct |
385 ms |
221440 KB |
Output is correct |
6 |
Correct |
1199 ms |
221440 KB |
Output is correct |
7 |
Correct |
1440 ms |
221440 KB |
Output is correct |
8 |
Correct |
1204 ms |
221440 KB |
Output is correct |
9 |
Correct |
2216 ms |
221440 KB |
Output is correct |
10 |
Correct |
1068 ms |
221440 KB |
Output is correct |
11 |
Correct |
1105 ms |
221440 KB |
Output is correct |
12 |
Correct |
792 ms |
221440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
47608 KB |
Output is correct |
2 |
Correct |
64 ms |
47608 KB |
Output is correct |
3 |
Correct |
76 ms |
47632 KB |
Output is correct |
4 |
Correct |
63 ms |
47728 KB |
Output is correct |
5 |
Correct |
63 ms |
47824 KB |
Output is correct |
6 |
Correct |
72 ms |
47848 KB |
Output is correct |
7 |
Correct |
87 ms |
47980 KB |
Output is correct |
8 |
Correct |
73 ms |
47980 KB |
Output is correct |
9 |
Correct |
67 ms |
47980 KB |
Output is correct |
10 |
Correct |
76 ms |
48008 KB |
Output is correct |
11 |
Correct |
70 ms |
48068 KB |
Output is correct |
12 |
Correct |
75 ms |
48072 KB |
Output is correct |
13 |
Correct |
105 ms |
48928 KB |
Output is correct |
14 |
Correct |
119 ms |
48932 KB |
Output is correct |
15 |
Correct |
88 ms |
49084 KB |
Output is correct |
16 |
Correct |
68 ms |
49492 KB |
Output is correct |
17 |
Correct |
98 ms |
49492 KB |
Output is correct |
18 |
Correct |
88 ms |
49492 KB |
Output is correct |
19 |
Correct |
84 ms |
49492 KB |
Output is correct |
20 |
Correct |
86 ms |
49664 KB |
Output is correct |
21 |
Correct |
77 ms |
49716 KB |
Output is correct |
22 |
Correct |
75 ms |
50288 KB |
Output is correct |
23 |
Correct |
1936 ms |
110756 KB |
Output is correct |
24 |
Correct |
935 ms |
125980 KB |
Output is correct |
25 |
Correct |
976 ms |
140572 KB |
Output is correct |
26 |
Correct |
633 ms |
140640 KB |
Output is correct |
27 |
Correct |
798 ms |
155600 KB |
Output is correct |
28 |
Correct |
1043 ms |
166928 KB |
Output is correct |
29 |
Correct |
1002 ms |
166928 KB |
Output is correct |
30 |
Correct |
904 ms |
167040 KB |
Output is correct |
31 |
Correct |
936 ms |
167040 KB |
Output is correct |
32 |
Correct |
749 ms |
167040 KB |
Output is correct |
33 |
Correct |
102 ms |
167040 KB |
Output is correct |
34 |
Correct |
173 ms |
167040 KB |
Output is correct |
35 |
Correct |
836 ms |
167040 KB |
Output is correct |
36 |
Correct |
1879 ms |
167040 KB |
Output is correct |
37 |
Correct |
747 ms |
182560 KB |
Output is correct |
38 |
Correct |
2188 ms |
221440 KB |
Output is correct |
39 |
Correct |
717 ms |
221440 KB |
Output is correct |
40 |
Correct |
1130 ms |
221440 KB |
Output is correct |
41 |
Correct |
893 ms |
221440 KB |
Output is correct |
42 |
Correct |
856 ms |
221440 KB |
Output is correct |
43 |
Correct |
934 ms |
221440 KB |
Output is correct |
44 |
Correct |
81 ms |
221440 KB |
Output is correct |
45 |
Correct |
130 ms |
221440 KB |
Output is correct |
46 |
Correct |
193 ms |
221440 KB |
Output is correct |
47 |
Correct |
223 ms |
221440 KB |
Output is correct |
48 |
Correct |
385 ms |
221440 KB |
Output is correct |
49 |
Correct |
1199 ms |
221440 KB |
Output is correct |
50 |
Correct |
1440 ms |
221440 KB |
Output is correct |
51 |
Correct |
1204 ms |
221440 KB |
Output is correct |
52 |
Correct |
2216 ms |
221440 KB |
Output is correct |
53 |
Correct |
1068 ms |
221440 KB |
Output is correct |
54 |
Correct |
1105 ms |
221440 KB |
Output is correct |
55 |
Correct |
792 ms |
221440 KB |
Output is correct |
56 |
Correct |
162 ms |
221440 KB |
Output is correct |
57 |
Correct |
329 ms |
221440 KB |
Output is correct |
58 |
Correct |
426 ms |
221440 KB |
Output is correct |
59 |
Correct |
1983 ms |
221440 KB |
Output is correct |
60 |
Correct |
3232 ms |
221440 KB |
Output is correct |
61 |
Correct |
1161 ms |
221440 KB |
Output is correct |
62 |
Correct |
1167 ms |
221440 KB |
Output is correct |
63 |
Correct |
2834 ms |
221440 KB |
Output is correct |
64 |
Correct |
1720 ms |
221440 KB |
Output is correct |
65 |
Correct |
1350 ms |
221440 KB |
Output is correct |
66 |
Correct |
1887 ms |
221440 KB |
Output is correct |
67 |
Correct |
1633 ms |
221440 KB |
Output is correct |
68 |
Correct |
1327 ms |
221440 KB |
Output is correct |
69 |
Correct |
3162 ms |
233352 KB |
Output is correct |