Submission #1183569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183569		steveonalex	Tiles (BOI24_tiles)	C++20	100 / 100	163 ms	26068 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()

ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}

ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}

template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }

template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }

template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }

template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 6e5 + 69;
vector<pair<int,int>> queries[N];

int odd_range = 0;
set<pair<int,int>> S[2];

int del_range(int idx, pair<int,int> v){
    int proc = 0;
    while(true){
        auto it = S[idx].lower_bound(make_pair(v.first, -1));
        if (it == S[idx].begin()) break;
        it--;
        pair<int, int> cur = *it;
        if (cur.second <= v.first) break;
        proc++;
        S[idx].erase(cur);
        if ((cur.second - cur.first) % 2 == 1) odd_range--;

        if (cur.second > v.second){
            pair<int, int> left = make_pair(cur.first, v.first);
            pair<int, int> right = make_pair(v.second, cur.second);

            S[idx].insert(left); S[idx].insert(right);
            if ((left.second - left.first) % 2 == 1) odd_range++;
            if ((right.second - right.first) % 2 == 1) odd_range++;
        }
        else{
            minimize(cur.second, v.first);
            S[idx].insert(cur);
            if ((cur.second - cur.first) % 2 == 1) odd_range++;
        }
    }
    while(true){
        auto it = S[idx].lower_bound(make_pair(v.first, -1));
        if (it == S[idx].end()) break;
        pair<int, int> cur = *it;
        if (cur.first >= v.second) break;
        proc++;

        S[idx].erase(cur);
        if ((cur.second - cur.first) % 2 == 1) odd_range--;

        if (cur.second > v.second){
            maximize(cur.first, v.second);
            S[idx].insert(cur);
            if ((cur.second - cur.first) % 2 == 1) odd_range++;
        }
    }
    return proc > 0;
}

void add_range(int idx, pair<int, int> v){
    auto it = S[idx].lower_bound(v);
    if (it != S[idx].end() && (*it).first == v.second) {
        pair<int, int> cur = *it;
        S[idx].erase(cur);
        if ((cur.second - cur.first) % 2 == 1) odd_range--;

        v.second = cur.second;
    }

    it = S[idx].lower_bound(v);
    if (it != S[idx].begin()){
        it--;
        if ((*it).second == v.first){
            pair<int,int> cur = *it;
            S[idx].erase(cur);
            if ((cur.second - cur.first) % 2 == 1) odd_range--;


            v.first = cur.first;
        }
    }


    S[idx].insert(v);
    if ((v.second - v.first) % 2 == 1) odd_range++;
}

int solve(){
    int n, m; cin >> n >> m;
    vector<pair<int,int>> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i].first >> a[i].second;

    vector<int> X;
    X.push_back(0);
    X.push_back(m);
    for(pair<int,int> i: a){
        if (i.first > 0) X.push_back(i.first - 1);
        X.push_back(i.first);
        if (i.first < m) X.push_back(i.first + 1);
    }
    remove_dup(X);

    for(int i = 0; i < n; ++i){
        int j = (i + 1) % n;
        if (a[i].first == a[j].first){
            int idx = lower_bound(ALL(X), a[i].first) - X.begin();
            int l = a[i].second, r = a[j].second;
            if (l > r) swap(l, r);
            queries[idx].push_back(make_pair(l, r));
        }
    }

    int ans = 0;

    for(int i = 0; i < (int) X.size(); ++i){
        int cur_parity = X[i] % 2;

        if (S[1 - cur_parity].empty()) maximize(ans, X[i]);
        for(pair<int, int> j: queries[i]){
            int cnt0 = del_range(0, j), cnt1 = del_range(1, j);
            if (cnt0 && cnt1) return ans;
            if (cur_parity == 0 && cnt1) return ans;
            if (cur_parity == 1 && cnt0) return ans;
            if (cnt0 + cnt1 == 0){
                add_range(cur_parity, j);
            }
        }

        if (odd_range > 0) return ans;
    }

    return ans;
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

    clock_t start = clock();

    cout << solve() << "\n";

    cerr << "Time elapsed: " << clock() - start << "ms!\n";
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 22 / 22
• Subtask 6: 25 / 25
• Subtask 7: 10 / 10