Submission #1105895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105895		WeIlIaN	Towers (NOI22_towers)	C++14	100 / 100	749 ms	155856 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()

#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;

const int M = 1e6+5;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vpii cities(n);
    vvi X(M);
    REP(i, n) {
        int x, y;
        cin>>x>>y;
        cities[i] = {x, y};
        X[x].pushb(y);
    }
    REP(i, M) {
        sort(all(X[i]));
    }
    vpii up(M, {M, M}), down(M);
    vpii chose(M, {-1, -1});
    REP(i, M) {
        int l = X[i].size();
        if(l == 0) {
            continue;
        }
        up[X[i][0]] = min(up[X[i][0]], {i, 0});
        down[X[i][0]] = max(down[X[i][0]], {i, 0});
        up[X[i][l-1]] = min(up[X[i][l-1]], {i, l-1});
        down[X[i][l-1]] = max(down[X[i][l-1]], {i, l-1});
        chose[i] = {0, l-1};
    }
    auto check = [&](int x, int y) -> bool {
        return (up[y].fir < x && x < down[y].fir);
    };
    qpii rem;
    REP(i, M) {
        int l = X[i].size();
        if(l == 0) {
            continue;
        }
        if(check(i, X[i][0])) {
            rem.push({i, 0});
            //cerr<<i<<' ';
        }
        if(l > 1 && check(i, X[i][l-1])) {
            rem.push({i, l-1});
            //cerr<<i<<' ';
        }
    }
    while(!rem.empty()) {
        auto [x, ind] = rem.front();
        rem.pop();
        auto [a, b] = chose[x];
        if(a == ind) {
            do {
                a++;
            } while(a <= b && check(x, X[x][a]));
            if(a > b) {
                chose[x] = {-1, -1};
                continue;
            }
            if(x < up[X[x][a]].fir) {
                if(up[X[x][a]].fir != down[X[x][a]].fir) {
                    rem.push(up[X[x][a]]);
                }
                up[X[x][a]] = {x, a};
            }
            if(down[X[x][a]].fir < x) {
                if(up[X[x][a]].fir != down[X[x][a]].fir) {
                    rem.push(down[X[x][a]]);
                }
                down[X[x][a]] = {x, a};
            }
        }
        else {
            do {
                b--;
            } while(a <= b && check(x, X[x][b]));
            if(a > b) {
                chose[x] = {-1, -1};
                continue;
            }
            if(x < up[X[x][b]].fir) {
                if(up[X[x][b]].fir != down[X[x][b]].fir) {
                    rem.push(up[X[x][b]]);
                }
                up[X[x][b]] = {x, b};
            }
            if(down[X[x][b]].fir < x) {
                if(up[X[x][b]].fir != down[X[x][b]].fir) {
                    rem.push(down[X[x][b]]);
                }
                down[X[x][b]] = {x, b};
            }
        }
        chose[x] = {a, b};
    }
    /*
    REP(i, 11) {
        cerr<<up[i].fir<<' '<<down[i].fir<<endl;
    }
    */
    map<pii, bool> ans;
    REP(i, M) {
        if(chose[i].fir == -1) {
            continue;
        }
        ans[{i, X[i][chose[i].fir]}] = true;
        ans[{i, X[i][chose[i].sec]}] = true;
    }
    REP(i, n) {
        if(ans[cities[i]]) {
            cout<<1;
        }
        else {
            cout<<0;
        }
    }
}

/*
16
9 10
2 10
5 10
6 3
6 1
5 8
6 7
9 8
4 3
6 10
4 8
2 7
2 1
5 7
4 1
9 3
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:103:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         auto [x, ind] = rem.front();
      |              ^
Main.cpp:105:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |         auto [a, b] = chose[x];
      |              ^

• 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