# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
612502 |
2022-07-29T16:08:43 Z |
fvogel499 |
Seats (IOI18_seats) |
C++17 |
|
268 ms |
98148 KB |
#include "seats.h"
#include <bits/stdc++.h>
#define size(x) (int)((x).size())
using namespace std;
const int p2 = 1<<20;
struct SumSegtree {
SumSegtree() {
t = new int [p2*2];
lz = new int [p2*2];
for (int i = 0; i < p2*2; i++) {
t[i] = 0;
lz[i] = 0;
}
}
void push(int x, int span) {
if (x < p2) {
lz[x*2] ^= lz[x];
lz[x*2+1] ^= lz[x];
}
if (lz[x]) {
t[x] = span-t[x];
lz[x] = 0;
}
}
void pull(int x) {
t[x] = t[x*2] + t[x*2+1];
}
void upd(int rb, int re, int qn = 1, int qb = 0, int qe = p2-1) {
if (rb > qe || qb > re) push(qn, qe-qb+1);
else if (rb <= qb && qe <= re) {
lz[qn] ^= 1;
push(qn, qe-qb+1);
}
else {
push(qn, qe-qb+1);
int qm = (qb+qe)/2;
upd(rb, re, qn*2, qb, qm);
upd(rb, re, qn*2+1, qm+1, qe);
pull(qn);
}
}
int get(int rb, int re, int qn = 1, int qb = 0, int qe = p2-1) {
push(qn, qe-qb+1);
if (rb > qe || qb > re) return 0;
else if (rb <= qb && qe <= re) {
return t[qn];
}
else {
int qm = (qb+qe)/2;
int r = get(rb, re, qn*2, qb, qm)+get(rb, re, qn*2+1, qm+1, qe);
pull(qn);
return r;
}
}
void set(int x, int val) {
int cur = get(x, x);
if (cur != val) {
upd(x, x);
}
}
int* t, * lz;
};
struct MaxSegtree {
MaxSegtree() {
t = new int [p2*2];
for (int i = 0; i < p2*2; i++) {
t[i] = -1;
}
}
void upd(int x, int v) {
x += p2;
t[x] = v;
for (x /= 2; x; x /= 2) {
t[x] = max(t[x*2], t[x*2+1]);
}
}
int get(int b, int e) {
int r = -1;
b += p2;
e += p2;
while (b <= e) {
if (b%2 == 1) {
r = max(r, t[b]);
b++;
}
if (e%2 == 0) {
r = max(r, t[e]);
e--;
}
b /= 2;
e /= 2;
}
return r;
}
int* t;
};
SumSegtree sumST = SumSegtree();
MaxSegtree maxST = MaxSegtree();
int n;
vector<int> posOf;
void give_initial_chart(int H, int W, std::vector<int> row, std::vector<int> col) {
assert(H == 1);
n = W;
assert(size(row) == n && size(col) == n);
posOf = vector<int>(n);
for (int i = 0; i < n; i++) {
assert(row[i] == 0);
posOf[col[i]] = i;
}
int range [2] = {posOf[0], posOf[0]};
for (int i = 0; i < n; i++) {
range[0] = min(range[0], posOf[i]);
range[1] = max(range[1], posOf[i]);
sumST.set(i, (range[1]-range[0] == i));
}
int log = sumST.get(0, p2-1);
for (int i = 0; i < n; i++) {
maxST.upd(posOf[i], i);
}
}
int swap_seats(int a, int b) {
assert(a >= 0 && a < n && b >= 0 && b < n);
if (a > b) swap(a, b);
assert(a < b);
if (a <= b-1) {
sumST.upd(a, b-1);
}
int lft = min(posOf[a], posOf[b]);
int rgt = max(posOf[a], posOf[b]);
if (lft+1 <= rgt-1) {
int len = (rgt-1)-(lft+1)+2;
if (max(a, maxST.get(lft+1, rgt-1)) == len-1) {
sumST.set(len-1, 1);
}
else {
sumST.set(len-1, 0);
}
}
sumST.set(0, 1);
int res = sumST.get(0, p2-1);
maxST.upd(posOf[a], b);
maxST.upd(posOf[b], a);
swap(posOf[a], posOf[b]);
return res;
}
Compilation message
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:123:9: warning: unused variable 'log' [-Wunused-variable]
123 | int log = sumST.get(0, p2-1);
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
36 ms |
50416 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
36 ms |
50416 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
268 ms |
98148 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
41 ms |
50856 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
90 ms |
26708 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
36 ms |
50416 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |