Submission #609742

#	Time	Username	Problem	Language	Result	Execution time	Memory
609742		MohamedFaresNebili	자리 배치 (IOI18_seats)	C++14	17 / 100	4072 ms	63832 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"

            using namespace std;

            int H, W, ST[4000004];
            array<int, 4> P[4000004];
            vector<int> R, C;

            void update(int v, int l, int r, int p, int val) {
                if(l == r) {
                    ST[v] = val;
                    return;
                }
                int md = (l + r) / 2;
                if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
                else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
                ST[v] = ST[v * 2] + ST[v * 2 + 1];
            }
            int query(int v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return 0;
                if(l >= lo && r <= hi) return ST[v];
                return query(v * 2, l, (l + r) / 2, lo, hi)
                    +  query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
            }
            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);
                int r1 = R[0], r2 = R[0];
                int c1 = C[0], c2 = C[0];
                for(int l = 0; l < H * W; l++) {
                    r1 = min(r1, R[l]); r2 = max(r2, R[l]);
                    c1 = min(c1, C[l]); c2 = max(c2, C[l]);
                    int cur = (r2 - r1 + 1) * (c2 - c1 + 1);
                    update(1, 0, H * W - 1, l, (cur == l + 1));
                    P[l] = {r1, r2, c1, c2};
                }
            }
            int swap_seats(int A, int B) {
              	if(A > B) swap(A, B);
                swap(R[A], R[B]); swap(C[A], C[B]);
                int r1 = (A > 0 ? P[A - 1][0] : H * W), r2 = (A > 0 ? P[A - 1][1] : 0);
                int c1 = (A > 0 ? P[A - 1][2] : H * W), c2 = (A > 0 ? P[A - 1][3] : 0);
                for(int l = A; l <= B; l++) {
                    r1 = min(r1, R[l]); r2 = max(r2, R[l]);
                    c1 = min(c1, C[l]); c2 = max(c2, C[l]);
                    int cur = (r2 - r1 + 1) * (c2 - c1 + 1);
                    update(1, 0, H * W - 1, l, (cur == l + 1));
                    P[l] = {r1, r2, c1, c2};
                }
                return ST[1];
            }

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