제출 #75319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75319		mammamia	자리 배치 (IOI18_seats)	C++14	0 / 100	346 ms	32784 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 100005;

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

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