Submission #631692

#	Time	Username	Problem	Language	Result	Execution time	Memory
631692		MohamedFaresNebili	Seats (IOI18_seats)	C++14	33 / 100	1599 ms	85836 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[6000005], cur[6000005], lazy[6000005];
                    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, 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(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 + 1);
                        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: 33 / 33
• Subtask 6: 0 / 30