제출 #1170262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170262		CDuong	Towers (NOI22_towers)	C++20	100 / 100	677 ms	195200 KiB

Main

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

void solve() {
    int n;
    cin >> n;

    const int mxA = 1e6;
    vector<array<int, 2>> a(n);
    vector<set<pair<int, int>>> row(mxA), col(mxA);
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        a[i] = {--x, --y};
        row[x].insert({y, i});
    }

    vector<int> res(n), pos(n);
    auto update = [&](auto &self, int idx, int val) -> void {
        auto [x, y] = a[idx];
        if (pos[idx] == 0) {
            col[y].insert({x, idx});
        }
        res[idx] = 1;
        pos[idx] |= val;
        if (isz(col[y]) < 3) {
            return;
        }
        assert(isz(col[y]) == 3);
        int ridx = next(col[y].begin())->second;
        auto [rx, ry] = a[ridx];
        col[ry].erase({rx, ridx});
        assert(row[rx].count({ry, ridx}));
        if (pos[ridx] == 1) {
            auto it = row[rx].lower_bound({ry, ridx});
            it = row[rx].erase(it);
            self(self, it->second, 1);
        }
        else if (pos[ridx] == 2) {
            auto it = row[rx].lower_bound({ry, ridx});
            it = prev(row[rx].erase(it));
            self(self, it->second, 2);
        }
        else {
            row[rx].erase({ry, ridx});
        }
        res[ridx] = pos[ridx] = 0;
    };

    for (int i = 0; i < mxA; ++i) if (not row[i].empty()) {
        update(update, row[i].begin()->second, 1);
        update(update, prev(row[i].end())->second, 2);
    }
    for (auto val : res) cout << val;
    cout << endl;
}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 31 / 31
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19