# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
828444 |
2023-08-17T09:32:46 Z |
vnm06 |
Seats (IOI18_seats) |
C++14 |
|
4000 ms |
76648 KB |
#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
int n;
int h, w;
int pos[1000005][2];
int mi_tree[4000005][2];
int ma_tree[4000005][2];
void update(int v, int le, int ri, int id)
{
if(ri<id || le>id) return;
if(le==ri)
{
mi_tree[v][0]=pos[le][0];
mi_tree[v][1]=pos[le][1];
ma_tree[v][0]=pos[le][0];
ma_tree[v][1]=pos[le][1];
}
else
{
int mid=(le+ri)/2;
update(2*v, le, mid, id);
update(2*v+1, mid+1, ri, id);
mi_tree[v][0]=min(mi_tree[2*v][0], mi_tree[2*v+1][0]);
mi_tree[v][1]=min(mi_tree[2*v][1], mi_tree[2*v+1][1]);
ma_tree[v][0]=max(ma_tree[2*v][0], ma_tree[2*v+1][0]);
ma_tree[v][1]=max(ma_tree[2*v][1], ma_tree[2*v+1][1]);
}
}
pair<pair<int, int>, pair<int, int> > query(int v, int le, int ri, int be, int en)
{
if(le>en || ri<be) return {{1e9, 0}, {1e9, 0}};
if(be<=le && ri<=en) return {{mi_tree[v][0], ma_tree[v][0]}, {mi_tree[v][1], ma_tree[v][1]}};
else
{
int mid=(le+ri)/2;
pair<pair<int, int>, pair<int, int> > pr1=query(2*v, le, mid, be, en), pr2=query(2*v+1, mid+1, ri, be, en);
return {{min(pr1.first.first, pr2.first.first), max(pr1.first.second, pr2.first.second)}, {min(pr1.second.first, pr2.second.first), max(pr1.second.second, pr2.second.second)}};
}
}
int br=0;
int ans[1000005];
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
h=H;
w=W;
n=h*w;
for(int i=0; i<n; i++) pos[i][0]=R[i], pos[i][1]=C[i];
for(int i=0; i<n; i++) update(1, 0, n-1, i);
for(int i=0; i<n; i++)
{
pair<pair<int, int>, pair<int, int> > pr=query(1, 0, n-1, 0, i);
int t=(pr.first.second-pr.first.first+1)*(pr.second.second-pr.second.first+1);
if(t==i+1) {ans[i]=1; br++;}
}
}
int swap_seats(int a, int b)
{
if(a>b) swap(a, b);
swap(pos[a][0], pos[b][0]);
swap(pos[a][1], pos[b][1]);
update(1, 0, n-1, a);
update(1, 0, n-1, b);
int mt=0;
for(int i=a; i<b; i++)
{
br-=ans[i];
ans[i]=0;
if(i<mt-1) continue;
pair<pair<int, int>, pair<int, int> > pr=query(1, 0, n-1, 0, i);
int t=(pr.first.second-pr.first.first+1)*(pr.second.second-pr.second.first+1);
if(t==i+1) {ans[i]=1; br++;}
if(t>mt) mt=t;
}
return br;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
6 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
396 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
340 KB |
Output is correct |
11 |
Correct |
4 ms |
408 KB |
Output is correct |
12 |
Correct |
10 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
6 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
396 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
340 KB |
Output is correct |
11 |
Correct |
4 ms |
408 KB |
Output is correct |
12 |
Correct |
10 ms |
340 KB |
Output is correct |
13 |
Correct |
32 ms |
1152 KB |
Output is correct |
14 |
Correct |
23 ms |
1108 KB |
Output is correct |
15 |
Correct |
23 ms |
1108 KB |
Output is correct |
16 |
Correct |
925 ms |
1136 KB |
Output is correct |
17 |
Correct |
24 ms |
1108 KB |
Output is correct |
18 |
Correct |
44 ms |
1148 KB |
Output is correct |
19 |
Correct |
206 ms |
1144 KB |
Output is correct |
20 |
Correct |
928 ms |
1140 KB |
Output is correct |
21 |
Correct |
936 ms |
1132 KB |
Output is correct |
22 |
Correct |
639 ms |
1228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2078 ms |
56676 KB |
Output is correct |
2 |
Correct |
2117 ms |
56688 KB |
Output is correct |
3 |
Correct |
2273 ms |
59200 KB |
Output is correct |
4 |
Correct |
2029 ms |
58580 KB |
Output is correct |
5 |
Correct |
2055 ms |
56672 KB |
Output is correct |
6 |
Correct |
2457 ms |
60532 KB |
Output is correct |
7 |
Correct |
2029 ms |
56680 KB |
Output is correct |
8 |
Correct |
2040 ms |
60476 KB |
Output is correct |
9 |
Correct |
2439 ms |
58552 KB |
Output is correct |
10 |
Correct |
2175 ms |
57996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
1108 KB |
Output is correct |
2 |
Correct |
70 ms |
6532 KB |
Output is correct |
3 |
Correct |
556 ms |
57932 KB |
Output is correct |
4 |
Correct |
555 ms |
56652 KB |
Output is correct |
5 |
Correct |
2394 ms |
60476 KB |
Output is correct |
6 |
Correct |
557 ms |
72628 KB |
Output is correct |
7 |
Correct |
589 ms |
76520 KB |
Output is correct |
8 |
Correct |
536 ms |
72624 KB |
Output is correct |
9 |
Correct |
566 ms |
72968 KB |
Output is correct |
10 |
Correct |
593 ms |
72632 KB |
Output is correct |
11 |
Correct |
1566 ms |
76648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
1352 KB |
Output is correct |
2 |
Correct |
30 ms |
1304 KB |
Output is correct |
3 |
Correct |
57 ms |
1376 KB |
Output is correct |
4 |
Correct |
407 ms |
1396 KB |
Output is correct |
5 |
Correct |
196 ms |
1992 KB |
Output is correct |
6 |
Execution timed out |
4091 ms |
60968 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
3 ms |
340 KB |
Output is correct |
4 |
Correct |
3 ms |
340 KB |
Output is correct |
5 |
Correct |
6 ms |
340 KB |
Output is correct |
6 |
Correct |
3 ms |
396 KB |
Output is correct |
7 |
Correct |
3 ms |
340 KB |
Output is correct |
8 |
Correct |
3 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
340 KB |
Output is correct |
11 |
Correct |
4 ms |
408 KB |
Output is correct |
12 |
Correct |
10 ms |
340 KB |
Output is correct |
13 |
Correct |
32 ms |
1152 KB |
Output is correct |
14 |
Correct |
23 ms |
1108 KB |
Output is correct |
15 |
Correct |
23 ms |
1108 KB |
Output is correct |
16 |
Correct |
925 ms |
1136 KB |
Output is correct |
17 |
Correct |
24 ms |
1108 KB |
Output is correct |
18 |
Correct |
44 ms |
1148 KB |
Output is correct |
19 |
Correct |
206 ms |
1144 KB |
Output is correct |
20 |
Correct |
928 ms |
1140 KB |
Output is correct |
21 |
Correct |
936 ms |
1132 KB |
Output is correct |
22 |
Correct |
639 ms |
1228 KB |
Output is correct |
23 |
Correct |
2078 ms |
56676 KB |
Output is correct |
24 |
Correct |
2117 ms |
56688 KB |
Output is correct |
25 |
Correct |
2273 ms |
59200 KB |
Output is correct |
26 |
Correct |
2029 ms |
58580 KB |
Output is correct |
27 |
Correct |
2055 ms |
56672 KB |
Output is correct |
28 |
Correct |
2457 ms |
60532 KB |
Output is correct |
29 |
Correct |
2029 ms |
56680 KB |
Output is correct |
30 |
Correct |
2040 ms |
60476 KB |
Output is correct |
31 |
Correct |
2439 ms |
58552 KB |
Output is correct |
32 |
Correct |
2175 ms |
57996 KB |
Output is correct |
33 |
Correct |
30 ms |
1108 KB |
Output is correct |
34 |
Correct |
70 ms |
6532 KB |
Output is correct |
35 |
Correct |
556 ms |
57932 KB |
Output is correct |
36 |
Correct |
555 ms |
56652 KB |
Output is correct |
37 |
Correct |
2394 ms |
60476 KB |
Output is correct |
38 |
Correct |
557 ms |
72628 KB |
Output is correct |
39 |
Correct |
589 ms |
76520 KB |
Output is correct |
40 |
Correct |
536 ms |
72624 KB |
Output is correct |
41 |
Correct |
566 ms |
72968 KB |
Output is correct |
42 |
Correct |
593 ms |
72632 KB |
Output is correct |
43 |
Correct |
1566 ms |
76648 KB |
Output is correct |
44 |
Correct |
19 ms |
1352 KB |
Output is correct |
45 |
Correct |
30 ms |
1304 KB |
Output is correct |
46 |
Correct |
57 ms |
1376 KB |
Output is correct |
47 |
Correct |
407 ms |
1396 KB |
Output is correct |
48 |
Correct |
196 ms |
1992 KB |
Output is correct |
49 |
Execution timed out |
4091 ms |
60968 KB |
Time limit exceeded |
50 |
Halted |
0 ms |
0 KB |
- |