Submission #1079753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079753		ainta	Sweeping (JOI20_sweeping)	C++17	100 / 100	10578 ms	546932 KiB

sweeping

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

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}


template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(_v % MD + MD); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<1000000007>;
template<> const Mint Mint::G = Mint(3);

#define N_ 1501000

struct Query{
    int type;
    int p, l;
    int x, y;
}U[N_];


pii Ans[N_];
pii w[N_];
int L,  Cur[N_];


priority_queue<pii, vector<pii> ,greater<pii> >PQX[N_], PQY[N_];
priority_queue<pii >PQX2[N_], PQY2[N_];
int MX[N_], MY[N_], Num[N_];

void DnC(int b, int e){
    if(b==e){
        if(U[b].type == 4){
            w[b] = {U[b].x,U[b].y};
        }
        return;
    }
    int m = (b+e)>>1;
    DnC(b,m);
    DnC(m+1,e);
    int cnt = 1;
    MX[1]=MY[1]=0;
    auto Put = [&](int nd, int idx){
        PQX[nd].push({w[idx].fi,idx});
        PQX2[nd].push({w[idx].fi,idx});
        PQY[nd].push({w[idx].se,idx});
        PQY2[nd].push({w[idx].se,idx});
        Num[idx] = nd;
    };
    rng(i,b,m){
        if(U[i].type == 4){
            Cur[i]=1;
            Put(cnt, i);
            Num[i] = cnt;
        }
    }

    set<int>SX;
    SX.insert(0);
    SX.insert(L+1);
    map<int,int>SM;
    SM[0] = 1;

    rng(i,m+1,e){
        if(U[i].type==1){
            int p = U[i].p;
            if(Cur[p]){
                Ans[i] = {max(w[p].fi, MX[Num[p]]), max(w[p].se, MY[Num[p]])};
            }
        }
        if(U[i].type==2){ // x < L-l && y <=l -> (L-l, y)
            int l = U[i].l;
            if(SX.find(L-l) != SX.end())continue;
            auto it2 = SX.lower_bound(L-l);
            auto it1 = prev(it2);
            int bx = *it1, ex = *it2;
            int nd = SM[*it1];

            vi Z1,Z2;
            int CK=0;

            while(1){
                while(!PQY[nd].empty()){
                    auto [y1, idx1] = PQY[nd].top();
                    if(Num[idx1] != nd){
                        PQY[nd].pop();
                        continue;
                    }
                    if(y1 > l){
                        cnt++;
                        SX.insert(L-l);
                        SM[L-l] = cnt;

                        MX[cnt] = L-l;
                        MY[cnt] = MY[nd];
                        
                        for(auto &idx : Z1){
                            Put(cnt, idx);
                        }
                        for(auto &idx : Z2){
                            PQY2[nd].push({w[idx].se,idx});
                        }
                        CK=1;
                        break;
                    }
                    Z1.pb(idx1);
                    PQY[nd].pop();
                    break;
                }
                if(CK)break;
                while(!PQY2[nd].empty()){
                    auto [y2, idx2] = PQY2[nd].top();
                    if(Num[idx2] != nd){
                        PQY2[nd].pop();
                        continue;
                    }
                    if(y2 <= l){
                        cnt++;
                        SX.insert(L-l);
                        SM[L-l] = nd;
                        SM[bx] = cnt;

                        MX[cnt] = MX[nd];
                        MY[cnt] = MY[nd];
                        MX[nd] = L-l;
                        
                        for(auto &idx : Z2){
                            Put(cnt, idx);
                        }
                        for(auto &idx : Z1){
                            PQY[nd].push({w[idx].se,idx});
                        }
                        CK=1;
                        break;
                    }
                    Z2.pb(idx2);
                    PQY2[nd].pop();
                    break;
                }
                if(CK || (PQY[nd].empty() && PQY2[nd].empty()))break;
            }
        }
        if(U[i].type==3){ // y < L-l && x <=l -> (x, L-l)
            int l = U[i].l;
            if(SX.find(l+1) != SX.end())continue;
            auto it2 = SX.lower_bound(l+1);
            auto it1 = prev(it2);
            int bx = *it1, ex = *it2;
            int nd = SM[*it1];

            vi Z1,Z2;
            int CK=0;

            while(1){
                while(!PQX[nd].empty()){
                    auto [x1, idx1] = PQX[nd].top();
                    if(Num[idx1] != nd){
                        PQX[nd].pop();
                        continue;
                    }
                    if(x1 > l){
                        cnt++;
                        SX.insert(l+1);
                        SM[bx] = cnt;
                        SM[l+1] = nd;

                        MY[cnt] = L-l;
                        MX[cnt] = MX[nd];
                        
                        for(auto &idx : Z1){
                            Put(cnt, idx);
                        }
                        for(auto &idx : Z2){
                            PQX2[nd].push({w[idx].fi,idx});
                        }
                        CK=1;
                        break;
                    }
                    Z1.pb(idx1);
                    PQX[nd].pop();
                    break;
                }
                if(CK)break;
                while(!PQX2[nd].empty()){
                    auto [x2, idx2] = PQX2[nd].top();
                    if(Num[idx2] != nd){
                        PQX2[nd].pop();
                        continue;
                    }
                    if(x2 <= l){
                        cnt++;
                        SX.insert(l+1);
                        SM[l+1] = cnt;

                        MY[cnt] = MY[nd];
                        MX[cnt] = MX[nd];
                        MY[nd] = L-l;
                        
                        for(auto &idx : Z2){
                            Put(cnt, idx);
                        }
                        for(auto &idx : Z1){
                            PQX[nd].push({w[idx].fi,idx});
                        }
                        CK=1;
                        break;
                    }
                    Z2.pb(idx2);
                    PQX2[nd].pop();
                    break;
                }
                if(CK || (PQX[nd].empty() && PQX2[nd].empty()))break;
            }
        }
    }
    rng(i,1,cnt){
        while(!PQX[i].empty())PQX[i].pop();
        while(!PQX2[i].empty())PQX2[i].pop();
        while(!PQY[i].empty())PQY[i].pop();
        while(!PQY2[i].empty())PQY2[i].pop();
    }
    rng(i,b,m){
        if(U[i].type == 4){
            w[i].fi = max(w[i].fi, MX[Num[i]]);
            w[i].se = max(w[i].se, MY[Num[i]]);
            Cur[i]=0;
        }
    }
}
int RN[N_];
void Solve(){
    int m, Q;
    scanf("%d%d%d",&L,&m,&Q);
    rng(i,1,m){
        scanf("%d%d",&U[i].x,&U[i].y);
        U[i].type = 4;
        RN[i]=i;
    }
    int cc = m;
    rng(i,m+1,m+Q){
        scanf("%d",&U[i].type);
        if(U[i].type == 1){
            scanf("%d",&U[i].p);
            U[i].p = RN[U[i].p];
        }
        if(U[i].type == 2){
            scanf("%d",&U[i].l);
        }
        if(U[i].type == 3){
            scanf("%d",&U[i].l);
        }
        if(U[i].type == 4){
            RN[++cc] = i;
            scanf("%d%d",&U[i].x,&U[i].y);
        }
    }
    DnC(1,m+Q);
    rng(i,1,m+Q){
        if(U[i].type==1)printf("%d %d\n",Ans[i].fi,Ans[i].se);
    }
}

int main(){
    int TC=1;
    //scanf("%d",&TC);
    while(TC--){
        Solve();
    }
}

Compilation message (stderr)

sweeping.cpp: In function 'void DnC(int, int)':
sweeping.cpp:136:28: warning: unused variable 'ex' [-Wunused-variable]
  136 |             int bx = *it1, ex = *it2;
      |                            ^~
sweeping.cpp:208:28: warning: unused variable 'ex' [-Wunused-variable]
  208 |             int bx = *it1, ex = *it2;
      |                            ^~
sweeping.cpp: In function 'void Solve()':
sweeping.cpp:293:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  293 |     scanf("%d%d%d",&L,&m,&Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
sweeping.cpp:295:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  295 |         scanf("%d%d",&U[i].x,&U[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:301:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  301 |         scanf("%d",&U[i].type);
      |         ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:303:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  303 |             scanf("%d",&U[i].p);
      |             ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:307:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  307 |             scanf("%d",&U[i].l);
      |             ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:310:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  310 |             scanf("%d",&U[i].l);
      |             ~~~~~^~~~~~~~~~~~~~
sweeping.cpp:314:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  314 |             scanf("%d%d",&U[i].x,&U[i].y);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25