제출 #1271606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271606		ZeroCool	Golf (JOI17_golf)	C++20	100 / 100	3171 ms	360964 KiB

golf

#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld long double
#define int long long
#define all(v) v.begin(), v.end()

// #pragma GCC optimize("O3,Ofast,unroll-loops ")

const int N = 5e5 + 20;
const int M = 20;
const int LOG = 20;
const int INF = 1e17;	
int MOD = 1e9 + 7;
const ld EPS = 1e-12;

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

struct SGT{
    vector<set<ar<int,3> > > s;
    int n;

    SGT(){}

    SGT(int _n){
        n = _n;
        s.resize(4 * n);
    }
    
    void upd(int k,int tl,int tr,int p, int l,int r){
        if(l > tr || tl > r)return;
        if(l <= tl && tr <= r){
            s[k].insert({p, l , r});
            return;
        }
        int tm = (tl + tr) / 2;
        upd(k * 2, tl, tm, p, l, r);
        upd(k * 2 + 1, tm + 1, tr, p, l, r);
    }
    void upd(int p,int l,int r){
        upd(1, 1, n, p, l, r);
    }

    void qry(int k,int tl,int tr, int p,int l,int r,vector<ar<int,3>> &v){
        for(auto it = s[k].lower_bound(ar<int,3>{l});it != s[k].end() && ((*it)[0] <= r);it = s[k].erase(it)){
            v.push_back(*it);
        }
        if(tl == tr)return;
        int tm = (tl + tr) / 2;
        if(p <= tm)qry(k * 2, tl, tm, p, l, r, v);
        else qry(k * 2 + 1, tm + 1, tr ,p, l, r, v);
    }

    vector<ar<int,3>> qry(int p,int l,int r){
        vector<ar<int,3> > res;
        qry(1, 1, n, p,  l, r, res);
        return res;
    }
    
};

struct CMP{
    vector<int> v;

    CMP(){
        v = {0, INF};
    }

    void add(int x){
        v.push_back(x);
    }

    void init(){
        sort(all(v));
        v.erase(unique(all(v)), v.end());
    }

    int get(int x){
        return lower_bound(all(v), x) - v.begin() + 1;
    }
};

void orz(){
    CMP cmp[2];
    ar<int,2> s, t;
    cin>>s[0]>>s[1]>>t[0]>>t[1];
    cmp[0].add(s[0]);
    cmp[0].add(t[0]);
    cmp[1].add(s[1]);
    cmp[1].add(t[1]);
    int n;
    cin>>n;
    vector<ar<int,3>> ev[2];
    for(int i = 0;i < n;i++){
        ar<int,2> a, b;
        cin>>a[0]>>b[0]>>a[1]>>b[1];
        cmp[0].add(a[0]);
        cmp[0].add(b[0]);
        cmp[1].add(a[1]);
        cmp[1].add(b[1]);
        for(int it = 0;it < 2;it++){
            for(auto u: {a[it], b[it]}){
                ev[it ^ 1].push_back({a[it  ^ 1], 1, u});
                ev[it ^ 1].push_back({b[it  ^ 1], -1, u});
                ev[it].push_back({u, 0, a[it ^ 1]});
            }
        }
    }
    cmp[0].init();
    cmp[1].init();

    for(int it = 0;it < 2;it++){
        for(auto &[a, b, c]: ev[it]){
            a = cmp[it].get(a);
            c = cmp[it ^ 1].get(c);
        }
    }

    s[0] = cmp[0].get(s[0]);
    t[0] = cmp[0].get(t[0]);
    s[1] = cmp[1].get(s[1]);
    t[1] = cmp[1].get(t[1]);
    SGT sgt[2];
    for(int i = 0;i < 2;i++){
        ev[i].push_back({s[i], 0, s[i ^ 1]});
        ev[i].push_back({t[i], 0, t[i ^ 1]});
        sgt[i] = SGT(cmp[i].v.size());
    }
    for(int it = 0;it < 2;it++){
        sort(all(ev[it]));
        set<int> s;
        s.insert(1);
        s.insert(cmp[it ^ 1].v.size());
        for(auto [a, b, c] : ev[it]){
            if(b == 1)s.insert(c);
            else if(b == -1)s.erase(c);
            else{
                auto i = s.lower_bound(c);
                int r = *i;
                --i;
                int l = *i;
                sgt[it ^ 1].upd(a, l, r);
            }
        }

    }
    queue<ar<int,4>> q;
    map<ar<int,4>,int> mp;
    for(int it = 0;it < 2;it++){
        auto C = sgt[it ^ 1].qry(s[it ^ 1], s[it], s[it]);
        for(auto [a, b, c]: C){
            mp[{it, a, b, c}] = 1;
            q.push({it, a, b, c});
        }
    }
    while(q.size()){
        auto [it, x, l, r] = q.front();
        q.pop();
        if(t[it] == x && l <= t[it ^ 1] && t[it ^ 1] <= r){
            cout<<mp[{it, x, l, r}];
            return;
        }
        auto C = sgt[it].qry(x, l, r);
        for(auto [a, b, c]: C){
            if(!mp.count({it ^ 1, a, b, c})){
                mp[{it ^ 1, a, b, c}] = mp[{it, x, l, r}] + 1;
                q.push({it ^ 1, a, b, c});
            }
        }
    }
    cout<<"lol\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //  cin>>t;
    while (t--)orz();
}   

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70