Submission #631660

#	Time	Username	Problem	Language	Result	Execution time	Memory
631660		MohamedFaresNebili	Seats (IOI18_seats)	C++14	0 / 100	240 ms	42188 KiB

seats

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

                    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) {
                        if(l == r) {
                            ST[v] = 0; cur[v] = 1; return;
                        }
                        build(v * 2, l, (l + r) / 2);
                        build(v * 2 + 1, (l + r) / 2 + 1, r);
                        cur[v] = cur[v * 2] + cur[v * 2];
                    }
                    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 > hi || r < lo) return;
                        if(l >= lo && r <= hi) {
                            ST[v] += val; lazy[v] += val;
                            prop(v, l, r); return;
                        }
                        update(v * 2, l, (l + r) / 2, lo, hi, val);
                        update(v * 2 + 1, (l + r) / 2 + 1, 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];
                    }
                    int calc(int i) {
                        int c = C[i], res = 0;
                        res += (c == 0 || A[c - 1] > i) ? 1 : -1;
                        res += (c == W - 1 || A[c + 1] > i) ? 1 : -1;
                        return res;
                    }

                    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;
                        build(1, 0, N - 1);
                        for(int l = 0; l < W; l++) {
                            update(1, 0, N - 1, l, N - 1, calc(l));
                        }
                    }
                    void upd(int c, int val) {
                        if(c < 0 || c >= W) return;
                        int i = A[c];
                        int v = calc(i);
                        update(1, 0, N - 1, A[c], N - 1, val * v);
                    }

                    int swap_seats(int a, int b) {
                        for(int i = -1; i <= 1; i++) {
                            upd(C[a] + i, -1);
                            upd(C[b] + i, -1);
                        }

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

                        for(int i = -1; i <= 1; i++) {
                            upd(C[a] + i, 1);
                            upd(C[b] + i, 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