Submission #75998

#	Time	Username	Problem	Language	Result	Execution time	Memory
75998		idLe	Seats (IOI18_seats)	C++14	0 / 100	674 ms	58452 KiB

seats

#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];
    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);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30