Submission #631762

#	Time	Username	Problem	Language	Result	Execution time	Memory
631762		MohamedFaresNebili	Seats (IOI18_seats)	C++14	100 / 100	3638 ms	135528 KiB

seats

#include <bits/stdc++.h>
 
                    using namespace std;
 
                    using ll = long long;
                    using ld = long double;
 
                    #define ff first
                    #define ss second
                    #define pb push_back
                    #define all(x) (x).begin(), (x).end()
                    #define lb lower_bound
 
                    const int oo = 1e9 + 7;
 
                    int N, H, W;
                    int ST[8000005], cur[8000005], lazy[8000005];
                    vector<vector<int>> A;
                    vector<int> R, C;
 
                    void build(int v, int l, int r) {
                        cur[v] = r - l;
                      	if(l + 1 == r) return;
                        build(v * 2, l, (l + r) / 2);
                        build(v * 2 + 1, (l + r) / 2, r);
                    }
                    void prop(int v, int l, int r) {
                        if(l == r) return;
                        lazy[v * 2] += lazy[v];
                        lazy[v * 2 + 1] += lazy[v];
 
                        ST[v * 2] += lazy[v];
                        ST[v * 2 + 1] += lazy[v];
                        lazy[v] = 0;
                    }
                    void update(int v, int l, int r, int lo, int hi, int val) {
                        prop(v, l, r);
                        if(l >= lo && r <= hi) {
                            ST[v] += val; lazy[v] += val;
                            prop(v, l, r); return;
                        }
                      	if(l >= hi || r <= lo) return;
                        update(v * 2, l, (l + r) / 2, lo, hi, val);
                        update(v * 2 + 1, (l + r) / 2, r, lo, hi, val);
                        ST[v] = min(ST[v * 2], ST[v * 2 + 1]); cur[v] = 0;
                        if(ST[v * 2] == ST[v]) cur[v] += cur[v * 2];
                        if(ST[v * 2 + 1] == ST[v]) cur[v] += cur[v * 2 + 1];
                    }
                    void update(pair<int, int> U, pair<int, int> V, int val) {
                        if(U.ff > V.ff) swap(U.ff, V.ff);
                        if(U.ss > V.ss) swap(U.ss, V.ss);
                        vector<int> arr(4);
                        arr[0] = (U.ff < 0 || U.ss < 0) ? N : A[U.ff][U.ss];
                        arr[1] = U.ff < 0 ? N : A[U.ff][V.ss];
                        arr[2] = U.ss < 0 ? N : A[V.ff][U.ss];
                        arr[3] = A[V.ff][V.ss];
                        sort(arr.begin(), arr.end());
                        update(1, 0, N, arr[0], arr[1], val);
                        update(1, 0, N, arr[2], arr[3], val);
                    }
                    void update(pair<int, int> U, int val) {
                        update({U.ff - 1, U.ss - 1}, U, val);
                        update({U.ff - 1, U.ss + 1}, U, val);
                        update({U.ff + 1, U.ss - 1}, U, val);
                        update({U.ff + 1, U.ss + 1}, U, val);
                    }
 
                    void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
                        H = h, W = w, N = H * W;
                        R = r, C = c; A.resize(H + 1, vector<int> (W + 1));
                        for(int l = 0; l < N; l++)
                            A[R[l]][C[l]] = l;
                        for(int l = 0; l <= W; l++)
                            A[H][l] = N;
                        for(int l = 0; l <= H; l++)
                            A[l][W] = N;
                        build(1, 0, N);
                        for(int l = 0; l <= H; l++) {
                            for(int i = 0; i <= W; i++)
                                update({l - 1, i - 1}, {l, i}, 1);
                        }
                    }
 
                    int swap_seats(int a, int b) {
                        update({R[a], C[a]}, -1);
                        update({R[b], C[b]}, -1);
 
                        swap(C[a], C[b]), swap(R[a], R[b]);
                        swap(A[R[a]][C[a]], A[R[b]][C[b]]);
 
                        update({R[a], C[a]}, 1);
                        update({R[b], C[b]}, 1);
 
                        return cur[1];
                    }

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