oj.uz

Submission #1079753

# Submission time Handle Problem Language Result Execution time Memory
1079753 2024-08-29T00:47:17 Z ainta Sweeping (JOI20_sweeping) C++17
100 / 100
 10578 ms 546932 KB 
#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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189268 KB Output is correct
2 Correct 68 ms 188752 KB Output is correct
3 Correct 68 ms 189016 KB Output is correct
4 Correct 75 ms 189120 KB Output is correct
5 Correct 83 ms 189140 KB Output is correct
6 Correct 70 ms 188840 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8295 ms 491388 KB Output is correct
2 Correct 8307 ms 499252 KB Output is correct
3 Correct 8507 ms 497260 KB Output is correct
4 Correct 3914 ms 345924 KB Output is correct
5 Correct 4102 ms 344756 KB Output is correct
6 Correct 6466 ms 489816 KB Output is correct
7 Correct 7769 ms 488096 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3362 ms 358396 KB Output is correct
2 Correct 2692 ms 345340 KB Output is correct
3 Correct 2494 ms 339060 KB Output is correct
4 Correct 2361 ms 337700 KB Output is correct
5 Correct 2767 ms 363888 KB Output is correct
6 Correct 2521 ms 337516 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3362 ms 358396 KB Output is correct
2 Correct 2692 ms 345340 KB Output is correct
3 Correct 2494 ms 339060 KB Output is correct
4 Correct 2361 ms 337700 KB Output is correct
5 Correct 2767 ms 363888 KB Output is correct
6 Correct 2521 ms 337516 KB Output is correct
7 Correct 5964 ms 455444 KB Output is correct
8 Correct 5824 ms 452180 KB Output is correct
9 Correct 5787 ms 467160 KB Output is correct
10 Correct 3210 ms 357980 KB Output is correct
11 Correct 3052 ms 337696 KB Output is correct
12 Correct 3279 ms 335988 KB Output is correct
13 Correct 3445 ms 339568 KB Output is correct
14 Correct 366 ms 212052 KB Output is correct
15 Correct 2246 ms 276712 KB Output is correct
16 Correct 6013 ms 467240 KB Output is correct
17 Correct 5846 ms 445184 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 189268 KB Output is correct
2 Correct 68 ms 188752 KB Output is correct
3 Correct 68 ms 189016 KB Output is correct
4 Correct 75 ms 189120 KB Output is correct
5 Correct 83 ms 189140 KB Output is correct
6 Correct 70 ms 188840 KB Output is correct
7 Correct 8295 ms 491388 KB Output is correct
8 Correct 8307 ms 499252 KB Output is correct
9 Correct 8507 ms 497260 KB Output is correct
10 Correct 3914 ms 345924 KB Output is correct
11 Correct 4102 ms 344756 KB Output is correct
12 Correct 6466 ms 489816 KB Output is correct
13 Correct 7769 ms 488096 KB Output is correct
14 Correct 3362 ms 358396 KB Output is correct
15 Correct 2692 ms 345340 KB Output is correct
16 Correct 2494 ms 339060 KB Output is correct
17 Correct 2361 ms 337700 KB Output is correct
18 Correct 2767 ms 363888 KB Output is correct
19 Correct 2521 ms 337516 KB Output is correct
20 Correct 5964 ms 455444 KB Output is correct
21 Correct 5824 ms 452180 KB Output is correct
22 Correct 5787 ms 467160 KB Output is correct
23 Correct 3210 ms 357980 KB Output is correct
24 Correct 3052 ms 337696 KB Output is correct
25 Correct 3279 ms 335988 KB Output is correct
26 Correct 3445 ms 339568 KB Output is correct
27 Correct 366 ms 212052 KB Output is correct
28 Correct 2246 ms 276712 KB Output is correct
29 Correct 6013 ms 467240 KB Output is correct
30 Correct 5846 ms 445184 KB Output is correct
31 Correct 6032 ms 546932 KB Output is correct
32 Correct 8141 ms 482116 KB Output is correct
33 Correct 8320 ms 508464 KB Output is correct
34 Correct 10578 ms 489668 KB Output is correct
35 Correct 10428 ms 493088 KB Output is correct
36 Correct 4522 ms 371372 KB Output is correct
37 Correct 5027 ms 354372 KB Output is correct
38 Correct 5277 ms 362052 KB Output is correct
39 Correct 5350 ms 361028 KB Output is correct
40 Correct 7815 ms 475768 KB Output is correct