Submission #95278

#	Time	Username	Problem	Language	Result	Execution time	Memory
95278		onjo0127	Seats (IOI18_seats)	C++11	100 / 100	2162 ms	145848 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second

struct Node { int mn, mnc; };
struct Segtree {
    vector<Node> tree;
    vector<int> lazy;
    void pull(int idx) {
        Node lc = tree[idx*2], rc = tree[idx*2+1];
        if(lc.mn < rc.mn) tree[idx] = lc;
        if(lc.mn > rc.mn) tree[idx] = rc;
        if(lc.mn == rc.mn) tree[idx] = {lc.mn, lc.mnc + rc.mnc};
    }
    void init(vector<int>& A, int idx, int s, int e) {
        if(s == e) {
            tree[idx] = {A[s], 1};
            return;
        }
        int m = s+e >> 1;
        init(A, idx*2, s, m);
        init(A, idx*2+1, m+1, e);
        pull(idx);
    }
    void upd_lazy(int idx, int s, int e) {
        if(lazy[idx]) {
            tree[idx].mn += lazy[idx];
            if(s != e) {
                lazy[idx*2] += lazy[idx];
                lazy[idx*2+1] += lazy[idx];
            }
            lazy[idx] = 0;
        }
    }
    void upd(int idx, int s, int e, int l, int r, int y) {
        upd_lazy(idx, s, e);
        if(r < s || e < l) return;
        if(l <= s && e <= r) {
            lazy[idx] += y; upd_lazy(idx, s, e);
            return;
        }
        int m = s+e >> 1;
        upd(idx*2, s, m, l, r, y);
        upd(idx*2+1, m+1, e, l, r, y);
        pull(idx);
    }
};

const int dx[4] = {0, 0, 1, 1};
const int dy[4] = {0, 1, 0, 1};

int h, w;
Segtree seg;
vector<vector<int> > A;
vector<int> r, c;

pair<pii, pii> ch(int x, int y) {
    vector<int> S;
    for(int k=0; k<4; k++) S.push_back(A[x + dx[k]][y + dy[k]]);
    sort(S.begin(), S.end());
    return {{S[0], S[1] - 1}, {S[2], S[3] - 1}};
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    for(auto& it: R) ++it; for(auto& it: C) ++it;
    r = R; c = C; h = H; w = W;
    vector<int> P(H*W+2, 0);
    for(int i=0; i<=H+1; i++) A.push_back(vector<int>(W+2, H*W+1));
    for(int i=0; i<H*W; i++) A[R[i]][C[i]] = i+1;
    for(int i=0; i<=H; i++) {
        for(int j=0; j<=W; j++) {
            pii p1, p2; tie(p1, p2) = ch(i, j);
            ++P[p1.fi]; --P[p1.se + 1];
            ++P[p2.fi]; --P[p2.se + 1];
        }
    }
    for(int i=1, s=0; i<=H*W; i++) {
        s += P[i], P[i] = s;
    }
    seg.tree.resize(4*H*W); seg.lazy.resize(4*H*W);
    seg.init(P, 1, 1, H*W);
}

void update(int x, int y, int d) {
    for(int k=0; k<4; k++) {
        pii p1, p2; tie(p1, p2) = ch(x-dx[k], y-dy[k]);
        seg.upd(1, 1, h*w, p1.fi, p1.se, d);
        seg.upd(1, 1, h*w, p2.fi, p2.se, d);
    }
}

int swap_seats(int a, int b) {
    int ra = r[a], ca = c[a], rb = r[b], cb = c[b];
    update(ra, ca, -1); update(rb, cb, -1);
    swap(A[ra][ca], A[rb][cb]);
    swap(r[a], r[b]); swap(c[a], c[b]);
    update(ra, ca, +1); update(rb, cb, +1);
    if(seg.tree[1].mn == 4) return seg.tree[1].mnc;
    return 0;
}

Compilation message (stderr)

seats.cpp: In member function 'void Segtree::init(std::vector<int>&, int, int, int)':
seats.cpp:23:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
seats.cpp: In member function 'void Segtree::upd(int, int, int, int, int, int)':
seats.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = s+e >> 1;
                 ~^~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:68:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto& it: R) ++it; for(auto& it: C) ++it;
     ^~~
seats.cpp:68:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto& it: R) ++it; for(auto& it: C) ++it;
                            ^~~

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