# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
75718 |
2018-09-10T19:06:56 Z |
idLe |
Seats (IOI18_seats) |
C++14 |
|
351 ms |
16064 KB |
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define LL (nod << 1)
#define RR LL | 1
#define fi first
#define se second
const int NMAX = 1000010;
vector<int> r;
pii arb[4*NMAX], seats[NMAX];
int lazy[4*NMAX], H, W, N, ar[NMAX];
void build(int nod, int st, int dr);
pii combine(pii a, pii b);
void updateAtPosition(int pos);
void lazy_update(int nod, int st, int dr, int l , int r, int val);
void propag(int nod);
void deleteAtPosition(int pos);
void give_initial_chart(int HH, int WW, vector<int> R, vector<int> C) {
H = HH; W = WW;
if (H != 1) return;
N = H * W;
build(1, 1, N);
for (int i=0; i<N; i++){
seats[i] = {1, C[i] + 1};
ar[C[i] + 1] = i + 1;
}
for (int i=2; i <= W + 1; i++)
updateAtPosition(i);
}
int swap_seats(int a, int b){
a = seats[a].se;
b = seats[b].se;
if (a > b) swap(a, b);
deleteAtPosition(a);
deleteAtPosition(a+1);
if (b > a + 1) deleteAtPosition(b);
deleteAtPosition(b+1);
swap(ar[a], ar[b]);
swap(seats[ar[a]-1], seats[ar[b]-1]);
updateAtPosition(a);
updateAtPosition(a+1);
if (b > a + 1) updateAtPosition(b);
updateAtPosition(b+1);
return (arb[1].fi == 1 ? arb[1].se : 0);
}
void deleteAtPosition(int pos){
if (pos < 2) return;
if (pos == W + 1) lazy_update(1, 1, N, ar[pos-1], N, -1);
else if (ar[pos] > ar[pos-1]) lazy_update(1, 1, N, ar[pos-1], ar[pos] - 1, -1);
}
pii combine(pii a, pii b){
if (a.fi < b.fi) return a;
if (b.fi < a.fi) return b;
return {a.fi, a.se + b.se};
}
void build(int nod, int st, int dr){
if (st == dr){
arb[nod] = {0, 1};
return;
}
int mid = (st + dr) >> 1;
build(LL, st, mid);
build(RR, mid + 1, dr);
arb[nod] = combine(arb[LL], arb[RR]);
}
void propag(int nod){
if (!lazy[nod]) return;
arb[nod].fi += lazy[nod];
if (LL <= 2*N - 1){
lazy[LL] += lazy[nod];
lazy[RR] += lazy[nod];
}
lazy[nod] = 0;
}
void lazy_update(int nod, int st, int dr, int l, int r, int val){
propag(nod);
if (st >= l && dr <= r){
lazy[nod] += val;
propag(nod);
return;
}
int mid = (st + dr) >> 1;
if (l <= mid) lazy_update(LL, st, mid, l, r, val);
if (r > mid) lazy_update(RR, mid+1, dr, l, r, val);
propag(LL); propag(RR);
arb[nod] = combine(arb[LL], arb[RR]);
}
void updateAtPosition(int pos){
if (pos < 2) return;
if (pos == W + 1) lazy_update(1, 1, N, ar[pos-1], N, 1);
else if (ar[pos] > ar[pos-1]) lazy_update(1, 1, N, ar[pos-1], ar[pos]-1, 1);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
351 ms |
16064 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
16064 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
16064 KB |
Output is correct |
2 |
Incorrect |
49 ms |
16064 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |