Submission #631689

#	Time	Username	Problem	Language	Result	Execution time	Memory
631689		MohamedFaresNebili	Seats (IOI18_seats)	C++14	0 / 100	241 ms	36088 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, ST[4000005], cur[4000005], lazy[4000005];
                    vector<int> R, C, A;
                    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) {
                        lazy[v * 2] += lazy[v];
                        lazy[v * 2 + 1] += lazy[v];
                        ST[v] += lazy[v]; lazy[v] = 0;
                    }
                    void pull(int v) {
                        int x = ST[v * 2] + lazy[v * 2], y = ST[v * 2 + 1] + lazy[v * 2 + 1];
                        ST[v] = min(x, y);
                        if(x == y) cur[v] = cur[v * 2] + cur[v * 2 + 1];
                        else if(x < y) cur[v] = cur[v * 2];
                        else cur[v] = cur[v * 2 + 1];
                    }
                    void update(int v, int l, int r, int lo, int hi, int val) {
                        if(l >= lo && r <= hi) {
                            lazy[v] += val;
                            return;
                        }
                      	if(l >= hi || r <= lo) return;
                      	prop(v);
                        update(v * 2, l, (l + r) / 2, lo, hi, val);
                        update(v * 2 + 1, (l + r) / 2, r, lo, hi, val);
                        pull(v);
                    }
                    void update(int i, int j, int val) {
                        i = (i >= 0 ? A[i] : N);
                        j = (j >= 0 ? A[j] : N);
                      	if(i > j) swap(i, j);
                        update(1, 0, N, i, j, 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(N);
                        for(int l = 0; l < W; l++) A[C[l]] = l;
                        A[N] = N; build(1, 0, N);
                        for(int l = 0; l <= N; l++) {
                            update(l - 1, l, 1);
                        }
                    }

                    int swap_seats(int a, int b) {
                        update(C[a] - 1, C[a], -1);
                        update(C[a], C[a] + 1, -1);

                        update(C[b] - 1, C[b], -1);
                        update(C[b], C[b] + 1, -1);

                        swap(C[a], C[b]), swap(A[C[a]], A[C[b]]);

                        update(C[a] - 1, C[a], 1);
                        update(C[a], C[a] + 1, 1);

                        update(C[b] - 1, C[b], 1);
                        update(C[b], C[b] + 1, 1);

                        return cur[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