Submission #683455

#	Time	Username	Problem	Language	Result	Execution time	Memory
683455		79brue	Seats (IOI18_seats)	C++17	64 / 100	3094 ms	262148 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int minV[1<<21], minC[1<<21], lazy[1<<21];

    void init(int i, int l, int r){
        lazy[i] = 0;
        if(l==r){
            minV[i] = 0, minC[i] = 1;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        minV[i] = 0, minC[i] = r-l+1;
    }

    void propagate(int i, int l, int r){
        minV[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void merge(int i){
        if(minV[i*2] == minV[i*2+1]) minV[i] = minV[i*2], minC[i] = minC[i*2] + minC[i*2+1];
        else if(minV[i*2] < minV[i*2+1]) minV[i] = minV[i*2], minC[i] = minC[i*2];
        else minV[i] = minV[i*2+1], minC[i] = minC[i*2+1];
    }

    void update(int i, int l, int r, int s, int e, int v){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += v;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, v);
        update(i*2+1, m+1, r, s, e, v);
        merge(i);
    }

    pair<int, int> query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s || e<l) return make_pair(1e9, 0);
        if(s<=l && r<=e) return make_pair(minV[i], minC[i]);
        int m = (l+r)>>1;
        pair<int, int> p1 = query(i*2, l, m, s, e);
        pair<int, int> p2 = query(i*2+1, m+1, r, s, e);
        if(p1.first == p2.first) return make_pair(p1.first, p1.second + p2.second);
        else if(p1.first < p2.first) return p1;
        else return p2;
    }
} tree;

int n, m;
vector<vector<int> > arr;
int R[1000002], C[1000002];
vector<vector<int> > st, en;
vector<vector<int> > st2, en2;

void update(int X, int Y, bool first=0){
    if(!first){
        tree.update(1, 0, n*m-1, st[X][Y], en[X][Y]-1, -1);
        tree.update(1, 0, n*m-1, st2[X][Y], en2[X][Y]-1, -5);
    }
    vector<int> v;
    for(int ti=X-1; ti<=X; ti++){
        for(int tj=Y-1; tj<=Y; tj++){
            if(ti<0||ti>=n||tj<0||tj>=m) continue;
            v.push_back(arr[ti][tj]);
        }
    }
    sort(v.begin(), v.end());
    st[X][Y] = v[0];
    en[X][Y] = ((int)v.size() <= 1) ? n*m : v[1];
    st2[X][Y] = ((int)v.size() <= 2) ? n*m : v[2];
    en2[X][Y] = ((int)v.size() <= 2) ? n*m : v[3];
    tree.update(1, 0, n*m-1, st[X][Y], en[X][Y]-1, 1);
    tree.update(1, 0, n*m-1, st2[X][Y], en2[X][Y]-1, 5);
}

void give_initial_chart(int H, int W, std::vector<int> _R, std::vector<int> _C){
    n = H, m = W;
    arr.resize(n);
    for(int i=0; i<n; i++) arr[i].resize(m);
    for(int i=0; i<n*m; i++){
        R[i] = _R[i], C[i] = _C[i];
        arr[R[i]][C[i]] = i;
    }
    tree.init(1, 0, n*m-1);

    st.resize(n+1), en.resize(n+1);
    st2.resize(n+1), en2.resize(n+1);
    for(int i=0; i<=n; i++){
        st[i].resize(m+1);
        st2[i].resize(m+1);
        en[i].resize(m+1);
        en2[i].resize(m+1);
        for(int j=0; j<=m; j++){
            update(i, j, 1);
        }
    }
}

int swap_seats(int a, int b){
    swap(arr[R[a]][C[a]], arr[R[b]][C[b]]);
    swap(R[a], R[b]);
    swap(C[a], C[b]);

    for(int x=R[a]; x<=R[a]+1; x++) for(int y=C[a]; y<=C[a]+1; y++) update(x, y);
    for(int x=R[b]; x<=R[b]+1; x++) for(int y=C[b]; y<=C[b]+1; y++) update(x, y);

    pair<int, int> p = tree.query(1, 0, n*m-1, 0, n*m-1);
    assert(p.first == 4);
    return p.second;
}

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