Submission #792071

#	Time	Username	Problem	Language	Result	Execution time	Memory
792071		1bin	Seats (IOI18_seats)	C++14	100 / 100	3195 ms	118976 KiB

seats

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

using namespace std;
 
#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1 << 20;
int n, lazy[b * 2];
pair<int, int> seg[b * 2];
vector<int> Y, X;
vector<vector<int>> v;
 
void upd_lazy(int ix, int l, int r){
    if(l >= n) return;
    if(seg[ix].first == b) seg[ix] = {0, min(n - 1, r) - l + 1};
    seg[ix].first += lazy[ix];
    if(l ^ r){
        lazy[ix * 2] += lazy[ix];
        lazy[ix * 2 + 1] += lazy[ix];
    }
    lazy[ix] = 0;
    return;
}
 
void upd(int ix, int nl, int nr, int l, int r, int v){
    upd_lazy(ix, nl, nr);
    if(nl > r || nr < l) return;
    if(nl >= l && nr <= r){
        lazy[ix] += v;
        upd_lazy(ix, nl, nr);
        return;
    }
    int m = (nl + nr) / 2;
    upd(ix * 2, nl, m, l, r, v);
    upd(ix * 2 + 1, m + 1, nr, l, r, v);
    seg[ix].first = min(seg[ix * 2].first, seg[ix * 2 + 1].first);
    seg[ix].second = (seg[ix * 2].first == seg[ix].first ? seg[ix * 2].second : 0) + (seg[ix * 2 + 1].first == seg[ix].first ? seg[ix * 2 + 1].second : 0);
    return;
}
 
void calc(int y, int x, int p){
    vector<int> t;
    for(int i = -1; i <= 0; i++)
        for(int j = -1; j <= 0; j++)
            t.emplace_back(v[y + i][x + j]);
    sort(all(t));
    upd(1, 0, b - 1, t[0], t[1] - 1, p);
    upd(1, 0, b - 1, t[2], t[3] - 1, p);
    return;
}
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    Y = R; X = C;
    n = H * W;
    v = vector<vector<int>> (H + 2, vector<int> (W + 2, n));
    for(int i = 0; i < n; i++) v[++Y[i]][++X[i]] = i;
    for(int i = 1; i < b * 2; i++) seg[i].first = b;
    for(int i = 1; i <= H + 1; i++)
        for(int j = 1; j <= W + 1; j++) calc(i, j, 1);
    return;
}
 
int swap_seats(int i1, int i2) {
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++){
            calc(Y[i1] + i, X[i1] + j, -1);
            calc(Y[i2] + i, X[i2] + j, -1);
        }
    swap(Y[i1], Y[i2]);
    swap(X[i1], X[i2]);
    swap(v[Y[i1]][X[i1]], v[Y[i2]][X[i2]]);
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++){
            calc(Y[i1] + i, X[i1] + j, 1);
            calc(Y[i2] + i, X[i2] + j, 1);
        }
    if(seg[1].first == 4) return seg[1].second;
    return 0;
}
 
/*
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    int n, m, q, a, b;
    cin >> n >> m >> q;
    vector<int> h(n * m), w(n * m);
    for(int i = 0; i < n * m; i++) cin >> h[i] >> w[i];
    give_initial_chart(n, m, h, w);
    cin >> q;
    while(q--){
        cin >> a >> b;
        cout << swap_seats(a, b) << '\n';
    }
    return 0;
}
*/

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