# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
75320 |
2018-09-09T08:49:08 Z |
mammamia |
Seats (IOI18_seats) |
C++14 |
|
722 ms |
58444 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1000005;
typedef pair<int, int> pii;
pii t[4*NMAX];
int lz[4*NMAX];
pii seats[1000555];
int tsz, H, W;
void updateAtPosition(int pos);
void deleteAtPosition(int pos);
void addInterval(int l, int r);
void subInterval(int l, int r);
vector<vector<int>> arr;
int ln(int n){
return 2*n;
}
int rn(int n){
return 2*n + 1;
}
pii tcombine(pii a, pii b){
if(a.first < b.first){
return a;
} else if(a.first > b.first) {
return b;
} else {
return {a.first, a.second + b.second};
}
}
void push(int n){
if(lz[n]){
t[n].first += lz[n];
lz[ln(n)] += lz[n];
lz[rn(n)] += lz[n];
lz[n] = 0;
}
}
void build(int n, int l, int r){
if(l == r){
t[n] = {0, 1};
return;
}
int pivot = (l+r)>>1;
build(ln(n), l, pivot);
build(rn(n), pivot + 1, r);
t[n] = tcombine(t[ln(n)], t[rn(n)]);
}
void update(int n, int l, int r, int ql, int qr, int add){
push(n);
if(ql <= l && r <= qr){
lz[n] += add;
push(n);
return;
}
int pivot = (l+r)>>1;
if(ql <= pivot)
update(ln(n), l, pivot, ql, qr, add);
if(qr > pivot)
update(rn(n), pivot+1, r, ql, qr, add);
push(ln(n));
push(rn(n));
t[n] = tcombine(t[ln(n)], t[rn(n)]);
}
void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
W = _W;
H = _H;
tsz = H*W; // add the right endpoint
build(1, 1, tsz);
arr.push_back(vector<int>(W+1, 0));
for(int i=0; i<W; ++i){
arr[0][C[i] + 1] = i + 1;
seats[i] = {1, C[i] + 1};
}
for(int i=2; i<=W+1; ++i){
updateAtPosition(i);
}
//cout<<"init: \n";
//cout<<t[1].first<<" "<<t[1].second<<"\n";
}
int swap_seats(int a, int b) {
a = seats[a].second;
b = seats[b].second;
if(a > b){
swap(a, b);
}
//cout<<"swap "<<a<<" "<<b<<"\n";
deleteAtPosition(a);
deleteAtPosition(a+1);
if(b > a + 1)
deleteAtPosition(b);
deleteAtPosition(b+1);
swap(arr[0][a], arr[0][b]);
swap(seats[arr[0][a]-1], seats[arr[0][b]-1]);
updateAtPosition(a);
updateAtPosition(a+1);
if(b > a + 1)
updateAtPosition(b);
updateAtPosition(b+1);
return (t[1].first == 1 ? t[1].second : 0);
}
void deleteAtPosition(int pos){
if(pos > 1) {
if(pos == W+1){
subInterval(arr[0][pos-1], tsz);
} else {
if (arr[0][pos] > arr[0][pos - 1]) {
subInterval(arr[0][pos - 1], arr[0][pos] - 1);
}
}
}
}
void updateAtPosition(int pos){
if(pos > 1) {
if(pos == W+1){
addInterval(arr[0][pos-1], tsz);
} else {
if (arr[0][pos] > arr[0][pos - 1]) {
addInterval(arr[0][pos - 1], arr[0][pos] - 1);
}
}
}
}
void addInterval(int l, int r){
//cout<<"add "<<l<<" "<<r<<"\n";
update(1, 1, tsz, l, r, +1);
}
void subInterval(int l, int r){
//cout<<"sub "<<l<<" "<<r<<"\n";
update(1, 1, tsz, l, r, -1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
371 ms |
32684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
32684 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
32684 KB |
Output is correct |
2 |
Correct |
44 ms |
32684 KB |
Output is correct |
3 |
Correct |
57 ms |
32684 KB |
Output is correct |
4 |
Correct |
78 ms |
32684 KB |
Output is correct |
5 |
Correct |
145 ms |
32684 KB |
Output is correct |
6 |
Incorrect |
722 ms |
58444 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |