Submission #609792

#	Time	Username	Problem	Language	Result	Execution time	Memory
609792		MohamedFaresNebili	Seats (IOI18_seats)	C++14	5 / 100	4088 ms	56820 KiB

seats

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "seats.h"
 
            using namespace std;
 
            int H, W;
            int X[2][4000004], Y[2][4000004];
            vector<int> R, C;
 
            void update(int v, int l, int r, int p, int val, int t) {
                if(l == r) {
                    X[t][v] = Y[t][v] = val;
                    return;
                }
                int md = (l + r) / 2;
                if(p <= md) update(v * 2, l, md, p, val, t);
                else update(v * 2 + 1, md + 1, r, p, val, t);
                X[t][v] = min(X[t][v * 2], X[t][v * 2 + 1]);
                Y[t][v] = max(Y[t][v * 2], Y[t][v * 2 + 1]);
            }
            pair<int, int> query(int v, int l, int r, int lo, int hi, int t) {
                if(l > hi || r < lo) return {-1, -1};
                if(l >= lo && r <= hi) return {X[t][v], Y[t][v]};
                pair<int, int> A = query(v * 2, l, (l + r) / 2, lo, hi, t);
                pair<int, int> B = query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, t);
                if(A.first == -1) return B;
                if(B.first == -1) return A;
                return {min(A.first, B.first), max(A.second, B.second)};
            }
 
            void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
                ::H = H; ::W = W;
                for(auto u : R) ::R.push_back(u);
                for(auto u : C) ::C.push_back(u);
                for(int l = 0; l < H * W; l++) {
                        update(1, 0, H * W - 1, l, R[l], 0);
                        update(1, 0, H * W - 1, l, C[l], 1);
                }
            }
            int swap_seats(int A, int B) {
                swap(R[A], R[B]); swap(C[A], C[B]);
              update(1, 0, H * W - 1, A, R[A], 0);
              update(1, 0, H * W - 1, A, C[A], 1);
              update(1, 0, H * W - 1, B, R[B], 0);
              update(1, 0, H * W - 1, B, C[B], 1);
              int res = 0;
              for(int l = 0; l < H * W; ) {
                pair<int, int> U = query(1, 0, H * W - 1, 0, l, 0);
                pair<int, int> V = query(1, 0, H * W - 1, 0, l, 1);
                int cur = (U.second - U.first + 1) * (V.second - V.first + 1);
                res += (cur == l + 1);
                if(cur == l + 1) l += min(U.second - U.first + 1, V.second - V.first + 1);
                else l = cur - 1;
              }
              return res;
            }

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