# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
91800 |
2018-12-30T04:10:01 Z |
Retro3014 |
Seats (IOI18_seats) |
C++17 |
|
3687 ms |
182040 KB |
#include "seats.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <deque>
#include <map>
using namespace std;
#define MAX_N 1000000
#define INF 1000000000
typedef long long ll;
struct S{
int x, y;
};
int h, w, N;
struct T{
int lazy;
int ans, mini;
int s, e;
int l, r;
};
vector<T> seg(1);
vector<S> v;
vector<int> r;
vector<S> s, e;
int ans;
vector<vector<int>> arr;
int tp=1;
void init(int x){
if(seg[x].s!=seg[x].e){
if(seg[x].l==-1){
seg[x].l=tp;
seg[tp]={0, (seg[x].s+seg[x].e)/2-seg[x].s+1, 0, seg[x].s, (seg[x].s+seg[x].e)/2, -1, -1};
tp++;
init(tp-1);
}
if(seg[x].r==-1){
seg[x].r=tp;
seg[tp]={0, seg[x].e-(seg[x].s+seg[x].e)/2, 0, (seg[x].s+seg[x].e)/2+1, seg[x].e, -1, -1};
tp++;
init(tp-1);
}
}
}
void update1(int idx){
if(idx==-1) return;
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy;
seg[seg[idx].l].mini += seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].lazy += seg[idx].lazy;
seg[seg[idx].r].mini += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
}
void update2(int idx){
if(idx==-1) return;
if(seg[idx].l==-1 && seg[idx].r==-1) return;
if(seg[idx].l==-1){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[idx].r==-1){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].l].mini;
}
void lazy_u(int idx, int x, int y, int z){
if(idx==-1) return;
if(seg[idx].lazy!=0){
if(seg[idx].l!=-1){
seg[seg[idx].l].lazy += seg[idx].lazy;
seg[seg[idx].l].mini += seg[idx].lazy;
}
if(seg[idx].r!=-1){
seg[seg[idx].r].lazy += seg[idx].lazy;
seg[seg[idx].r].mini += seg[idx].lazy;
}
seg[idx].lazy = 0;
}
if(seg[idx].s>=x && seg[idx].e<=y){
seg[idx].mini+=z;
seg[idx].lazy+=z; return;
}
if(seg[idx].e<x || seg[idx].s>y) return;
lazy_u(seg[idx].l, x, y, z);
lazy_u(seg[idx].r, x, y, z);
if(seg[idx].l==-1 && seg[idx].r==-1) return;
if(seg[idx].l==-1){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[idx].r==-1){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
if(seg[seg[idx].r].mini<seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].r].mini;
return;
}
if(seg[seg[idx].r].mini>seg[seg[idx].l].mini){
seg[idx].ans = seg[seg[idx].l].ans;
seg[idx].mini = seg[seg[idx].l].mini;
return;
}
seg[idx].ans = seg[seg[idx].l].ans + seg[seg[idx].r].ans;
seg[idx].mini = seg[seg[idx].l].mini;
}
vector<int> sq;
int dx[4]={-1, -1, 0, 0}, dy[4]={0, -1, 0, -1};
map<int, int> mp;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
seg[0]={0, H*W, 0, 0, H*W-1, -1, -1};
seg.resize(2*H*W);
init(0);
N=H*W;
h=H; w=W;
arr.resize(H);
for(int i=0; i<H; i++){
arr[i].resize(W);
}
for(int i=0; i<R.size(); i++){
v.push_back({R[i], C[i]});
arr[R[i]][C[i]]=i;
}
for(int i=0; i<=H; i++){
for(int j=0; j<=W; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<H && j+dy[k]>=0 && j+dy[k]<W){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
//lazy_u(0, sq[k], N, 1);
mp[sq[k]]++;
}else{
mp[sq[k]]--;
//lazy_u(0, sq[k], N, -1);
}
}
}
}
}
int swap_seats(int a, int b) {
for(int i=v[a].x; i<=v[a].x+1; i++){
for(int j=v[a].y; j<=v[a].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]-=1;
}else{
mp[sq[k]]+=1;
}
}
}
}
for(int i=v[b].x; i<=v[b].x+1; i++){
for(int j=v[b].y; j<=v[b].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]-=1;
//lazy_u(0, sq[k], N, -1);
}else{
mp[sq[k]]+=1;
//lazy_u(0, sq[k], N, 1);
}
}
}
}
S tmp = v[a]; v[a] = v[b]; v[b] = tmp;
arr[v[a].x][v[a].y]=a; arr[v[b].x][v[b].y]=b;
for(int i=v[a].x; i<=v[a].x+1; i++){
for(int j=v[a].y; j<=v[a].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]+=1;
//lazy_u(0, sq[k], N, 1);
}else{
mp[sq[k]]-=1;
//lazy_u(0, sq[k], N, -1);
}
}
}
}
for(int i=v[b].x; i<=v[b].x+1; i++){
for(int j=v[b].y; j<=v[b].y+1; j++){
while(!sq.empty()) sq.pop_back();
for(int k=0; k<4; k++){
if(i+dx[k]>=0 && i+dx[k]<h && j+dy[k]>=0 && j+dy[k]<w){
sq.push_back(arr[i+dx[k]][j+dy[k]]);
}
}
sort(sq.begin(), sq.end());
for(int k=0; k<sq.size(); k++){
if(k==0 || k==2){
mp[sq[k]]+=1;
//lazy_u(0, sq[k], N, 1);
}else{
mp[sq[k]]-=1;
//lazy_u(0, sq[k], N, -1);
}
}
}
}
for(map<int, int>::iterator it = mp.begin(); it!=mp.end(); it = mp.begin()){
if(it->second !=0) lazy_u(0, it->first, N, it->second);
mp.erase(it);
}
return seg[0].ans;
}
Compilation message
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<R.size(); i++){
~^~~~~~~~~
seats.cpp:165:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0; k<sq.size(); k++){
~^~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:189:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0; k<sq.size(); k++){
~^~~~~~~~~~
seats.cpp:207:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0; k<sq.size(); k++){
~^~~~~~~~~~
seats.cpp:229:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0; k<sq.size(); k++){
~^~~~~~~~~~
seats.cpp:249:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0; k<sq.size(); k++){
~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
376 KB |
Output is correct |
2 |
Correct |
22 ms |
376 KB |
Output is correct |
3 |
Correct |
26 ms |
376 KB |
Output is correct |
4 |
Correct |
12 ms |
504 KB |
Output is correct |
5 |
Correct |
10 ms |
376 KB |
Output is correct |
6 |
Correct |
21 ms |
468 KB |
Output is correct |
7 |
Correct |
24 ms |
424 KB |
Output is correct |
8 |
Correct |
25 ms |
380 KB |
Output is correct |
9 |
Correct |
26 ms |
376 KB |
Output is correct |
10 |
Correct |
25 ms |
412 KB |
Output is correct |
11 |
Correct |
21 ms |
376 KB |
Output is correct |
12 |
Correct |
11 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
376 KB |
Output is correct |
2 |
Correct |
22 ms |
376 KB |
Output is correct |
3 |
Correct |
26 ms |
376 KB |
Output is correct |
4 |
Correct |
12 ms |
504 KB |
Output is correct |
5 |
Correct |
10 ms |
376 KB |
Output is correct |
6 |
Correct |
21 ms |
468 KB |
Output is correct |
7 |
Correct |
24 ms |
424 KB |
Output is correct |
8 |
Correct |
25 ms |
380 KB |
Output is correct |
9 |
Correct |
26 ms |
376 KB |
Output is correct |
10 |
Correct |
25 ms |
412 KB |
Output is correct |
11 |
Correct |
21 ms |
376 KB |
Output is correct |
12 |
Correct |
11 ms |
380 KB |
Output is correct |
13 |
Correct |
42 ms |
1656 KB |
Output is correct |
14 |
Correct |
47 ms |
1656 KB |
Output is correct |
15 |
Correct |
25 ms |
1656 KB |
Output is correct |
16 |
Correct |
21 ms |
2168 KB |
Output is correct |
17 |
Correct |
37 ms |
1744 KB |
Output is correct |
18 |
Correct |
42 ms |
1656 KB |
Output is correct |
19 |
Correct |
34 ms |
1656 KB |
Output is correct |
20 |
Correct |
31 ms |
1912 KB |
Output is correct |
21 |
Correct |
25 ms |
1656 KB |
Output is correct |
22 |
Correct |
23 ms |
2228 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3137 ms |
129648 KB |
Output is correct |
2 |
Correct |
1439 ms |
129760 KB |
Output is correct |
3 |
Correct |
1248 ms |
130136 KB |
Output is correct |
4 |
Correct |
1203 ms |
130048 KB |
Output is correct |
5 |
Correct |
1109 ms |
130132 KB |
Output is correct |
6 |
Correct |
1354 ms |
130032 KB |
Output is correct |
7 |
Correct |
925 ms |
130108 KB |
Output is correct |
8 |
Correct |
1087 ms |
130072 KB |
Output is correct |
9 |
Correct |
1467 ms |
130024 KB |
Output is correct |
10 |
Correct |
1213 ms |
130136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
1784 KB |
Output is correct |
2 |
Correct |
130 ms |
12216 KB |
Output is correct |
3 |
Correct |
987 ms |
130404 KB |
Output is correct |
4 |
Correct |
2678 ms |
130244 KB |
Output is correct |
5 |
Correct |
1264 ms |
130776 KB |
Output is correct |
6 |
Correct |
3179 ms |
182040 KB |
Output is correct |
7 |
Correct |
1324 ms |
132920 KB |
Output is correct |
8 |
Correct |
1383 ms |
132956 KB |
Output is correct |
9 |
Correct |
1235 ms |
133284 KB |
Output is correct |
10 |
Correct |
1245 ms |
135864 KB |
Output is correct |
11 |
Correct |
1600 ms |
156736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
2008 KB |
Output is correct |
2 |
Correct |
88 ms |
2048 KB |
Output is correct |
3 |
Correct |
88 ms |
2052 KB |
Output is correct |
4 |
Correct |
110 ms |
2048 KB |
Output is correct |
5 |
Correct |
133 ms |
2980 KB |
Output is correct |
6 |
Correct |
1786 ms |
129940 KB |
Output is correct |
7 |
Correct |
1713 ms |
130040 KB |
Output is correct |
8 |
Correct |
1537 ms |
129876 KB |
Output is correct |
9 |
Correct |
3274 ms |
130008 KB |
Output is correct |
10 |
Correct |
1644 ms |
130084 KB |
Output is correct |
11 |
Correct |
1565 ms |
130020 KB |
Output is correct |
12 |
Correct |
1405 ms |
130004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
376 KB |
Output is correct |
2 |
Correct |
22 ms |
376 KB |
Output is correct |
3 |
Correct |
26 ms |
376 KB |
Output is correct |
4 |
Correct |
12 ms |
504 KB |
Output is correct |
5 |
Correct |
10 ms |
376 KB |
Output is correct |
6 |
Correct |
21 ms |
468 KB |
Output is correct |
7 |
Correct |
24 ms |
424 KB |
Output is correct |
8 |
Correct |
25 ms |
380 KB |
Output is correct |
9 |
Correct |
26 ms |
376 KB |
Output is correct |
10 |
Correct |
25 ms |
412 KB |
Output is correct |
11 |
Correct |
21 ms |
376 KB |
Output is correct |
12 |
Correct |
11 ms |
380 KB |
Output is correct |
13 |
Correct |
42 ms |
1656 KB |
Output is correct |
14 |
Correct |
47 ms |
1656 KB |
Output is correct |
15 |
Correct |
25 ms |
1656 KB |
Output is correct |
16 |
Correct |
21 ms |
2168 KB |
Output is correct |
17 |
Correct |
37 ms |
1744 KB |
Output is correct |
18 |
Correct |
42 ms |
1656 KB |
Output is correct |
19 |
Correct |
34 ms |
1656 KB |
Output is correct |
20 |
Correct |
31 ms |
1912 KB |
Output is correct |
21 |
Correct |
25 ms |
1656 KB |
Output is correct |
22 |
Correct |
23 ms |
2228 KB |
Output is correct |
23 |
Correct |
3137 ms |
129648 KB |
Output is correct |
24 |
Correct |
1439 ms |
129760 KB |
Output is correct |
25 |
Correct |
1248 ms |
130136 KB |
Output is correct |
26 |
Correct |
1203 ms |
130048 KB |
Output is correct |
27 |
Correct |
1109 ms |
130132 KB |
Output is correct |
28 |
Correct |
1354 ms |
130032 KB |
Output is correct |
29 |
Correct |
925 ms |
130108 KB |
Output is correct |
30 |
Correct |
1087 ms |
130072 KB |
Output is correct |
31 |
Correct |
1467 ms |
130024 KB |
Output is correct |
32 |
Correct |
1213 ms |
130136 KB |
Output is correct |
33 |
Correct |
39 ms |
1784 KB |
Output is correct |
34 |
Correct |
130 ms |
12216 KB |
Output is correct |
35 |
Correct |
987 ms |
130404 KB |
Output is correct |
36 |
Correct |
2678 ms |
130244 KB |
Output is correct |
37 |
Correct |
1264 ms |
130776 KB |
Output is correct |
38 |
Correct |
3179 ms |
182040 KB |
Output is correct |
39 |
Correct |
1324 ms |
132920 KB |
Output is correct |
40 |
Correct |
1383 ms |
132956 KB |
Output is correct |
41 |
Correct |
1235 ms |
133284 KB |
Output is correct |
42 |
Correct |
1245 ms |
135864 KB |
Output is correct |
43 |
Correct |
1600 ms |
156736 KB |
Output is correct |
44 |
Correct |
52 ms |
2008 KB |
Output is correct |
45 |
Correct |
88 ms |
2048 KB |
Output is correct |
46 |
Correct |
88 ms |
2052 KB |
Output is correct |
47 |
Correct |
110 ms |
2048 KB |
Output is correct |
48 |
Correct |
133 ms |
2980 KB |
Output is correct |
49 |
Correct |
1786 ms |
129940 KB |
Output is correct |
50 |
Correct |
1713 ms |
130040 KB |
Output is correct |
51 |
Correct |
1537 ms |
129876 KB |
Output is correct |
52 |
Correct |
3274 ms |
130008 KB |
Output is correct |
53 |
Correct |
1644 ms |
130084 KB |
Output is correct |
54 |
Correct |
1565 ms |
130020 KB |
Output is correct |
55 |
Correct |
1405 ms |
130004 KB |
Output is correct |
56 |
Correct |
142 ms |
2036 KB |
Output is correct |
57 |
Correct |
247 ms |
2180 KB |
Output is correct |
58 |
Correct |
392 ms |
3112 KB |
Output is correct |
59 |
Correct |
1808 ms |
130056 KB |
Output is correct |
60 |
Correct |
3600 ms |
130264 KB |
Output is correct |
61 |
Correct |
1846 ms |
130140 KB |
Output is correct |
62 |
Correct |
1547 ms |
130132 KB |
Output is correct |
63 |
Correct |
3687 ms |
130136 KB |
Output is correct |
64 |
Correct |
1935 ms |
130108 KB |
Output is correct |
65 |
Correct |
1355 ms |
129996 KB |
Output is correct |
66 |
Correct |
1971 ms |
130388 KB |
Output is correct |
67 |
Correct |
2087 ms |
133164 KB |
Output is correct |
68 |
Correct |
1708 ms |
144500 KB |
Output is correct |
69 |
Correct |
3292 ms |
153576 KB |
Output is correct |