oj.uz

Submission #926102

# Submission time Handle Problem Language Result Execution time Memory
926102 2024-02-12T14:58:51 Z manizare Sweeping (JOI20_sweeping) C++11
75 / 100
 7922 ms 2097152 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define ld long double
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ;
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 16e6 +  10 , maxp = 2e6 + 10, lg = 22 , mod = 998244353 ,  sq =700 , inf = 1e9 ;
int n,m,q,x[maxp] ,y[maxp] ,p[2][maxp] , cnt = 2 , c = 2 ;
vector <int> cm ; 
vector <int> g[2][maxp] ;
 
int f(int v,int t){
    return (p[t][v]==0 ? v : p[t][v]=f(p[t][v],t)); 
}
void mrg(int v,int u , int t){
    u = f(u,t) ; v = f(v,t);
    if(v==u)return ;
    p[t][v]= u ;
    g[t][u].pb(v);
}
 
void reval(int v){
    x[v] = x[f(v,0)];
    y[v] = y[f(v,1)];
}
vector <int> rem ; 
void dfs(int v,int r,int t) {
    rem.pb(v); 
    for(int u :g[t][v]){
        if(f(u,t)!=r)continue ;
        dfs(u,r,t) ;
    }
}
 
struct rec{
    set <pii> s[2] ;
    int X , Y , d  , cl , cr ;
    int gl(){
        if(cl==0){
            cl = c ;c++;
        }
        return cl ;
    }
    int gr(){
        if(cr==0){
            cr = c ;c++;
        }
        return cr ;
    }
    void add(int v){
        p[0][v] = p[1][v] = 0 ;
        g[0][v].clear() ;g[1][v].clear(); 
        s[0].insert({y[v] , v}) ;
        s[1].insert({x[v] , v}) ;
    }
    void ers(int v){
        s[0].erase({y[v] , v}) ;
        s[1].erase({x[v] , v});
    }
    void up1(int l ,int t){
        rem.clear() ;
        while(sz(s[!t]) && (*s[!t].begin()).F <= l){
            int v = (*s[!t].begin()).S ; 
            dfs(v,v,t) ;
            s[!t].erase(s[!t].begin()) ;
        }
        for(int id : rem){
            reval(id) ;
        }
        for(int id : rem){
            ers(id) ;
        }
        for(int id : rem){
            if(t == 0){
                y[id] = n-l ;
            }else{
                x[id] = n-l ; 
            }
        }
    }
    void up2(int l,int t){
        int maxi = n-l ;
        vector <pii> az; 
        while(sz(s[t]) && (*s[t].begin()).F <= maxi){
            int id = (*s[t].begin()).S;  
            if(t==0){
                reval(id);
                az.pb({x[id] , id});
            }else{
                reval(id);
                az.pb({y[id] , id}) ;  
            }
            s[t].erase(s[t].begin()) ; 
        }
        if(sz(az)==0)return ;
        sort(all(az));
        if(t==0){
            y[az.back().S] = maxi ;
        }else{ 
            x[az.back().S] = maxi ;
        }
        s[t].insert({maxi,az.back().S}) ; 
        rep(i , 0, sz(az)-2){
            mrg(az[i].S , az[i+1].S , !t); 
        }
    }
};
rec r[maxn] ;
 
void ADD(int id , int p = 1  , int X = 0 , int Y = 0 , int d =n){
    r[p].X = X ; r[p].Y = Y ; r[p].d = (d+1)/2 ;
    int m1 = X+(d+1)/2 ,  m2 = Y+(d+1)/2 ;
    if(d==0){
        r[p].add(id) ;
        return ; 
    }
    if(m1 > x[id] && m2 > y[id]){
        r[p].add(id) ;
        return ;
    }
    if(m1 <= x[id]){
        ADD(id , r[p].gr() , m1 , Y  , d/2); 
    }else{
        ADD(id , r[p].gl() , X , m2 , d/2) ; 
    }
}
void upd(int l , int t , int p = 1,int X= 0 , int Y= 0, int d= n){
    r[p].X = X ; r[p].Y = Y ; r[p].d = (d+1)/2 ;
    if(d==0)return ; 
    if((t==0 && X > l) || (t==1 && Y > l))return ;
    int m1 = X+(d+1)/2 ,  m2 = Y+(d+1)/2 ;
    if((t==0&& l+(d&1)<=m1) || (t==1&& l+(d&1)<=m2)){
        r[p].up1(l,t); 
        while(sz(rem)){
            int v = rem.back() ;
            ADD(v); 
            rem.pop_back() ;
        }
        if(t==0)upd(l , t ,r[p].gl() , X , m2 , d/2);
        else upd(l,t, r[p].gr() , m1 , Y , d/2) ;
    }
    if((t==0&&l >= m1) || (t==1&&l >= m2)){
        r[p].up2(l,t);
        if(t==0)upd(l, t , r[p].gr() , m1 , Y  , d/2); 
        else upd(l,t , r[p].gl() , X  , m2 , d/2) ;
    }
}
 
 
signed main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q ;
    int id = 1; 
    rep(i , 1 , m){
        cin >> x[id] >> y[id] ;
        ADD(id) ;
        id++;
    }
    while(q--){
        int t ;
        cin >> t ;
        if(t==1){
            int a ;cin >> a;
            reval(a);
            cout << x[a] << " " << y[a] << "\n" ; 
        }
        if(t==3){
            int l ;
            cin >> l ;
            upd(l , 0);   
        }
        if(t==2){
            int l ;
            cin >> l ;
            upd(l , 1);
        }
        if(t==4){
            cin >> x[id] >> y[id];
            ADD(id) ;
            id++;
        }
    }
    return 0;
}
 
/*
 
*/

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 1975052 KB Output is correct
2 Correct 672 ms 1975080 KB Output is correct
3 Correct 669 ms 1975076 KB Output is correct
4 Correct 670 ms 1975360 KB Output is correct
5 Correct 713 ms 1975220 KB Output is correct
6 Correct 671 ms 1974936 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3465 ms 2078468 KB Output is correct
2 Correct 3453 ms 2078256 KB Output is correct
3 Correct 3417 ms 2078548 KB Output is correct
4 Correct 2917 ms 2064920 KB Output is correct
5 Correct 7922 ms 2089212 KB Output is correct
6 Correct 6206 ms 2085264 KB Output is correct
7 Correct 3520 ms 2077344 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3721 ms 2080736 KB Output is correct
2 Correct 4157 ms 2079768 KB Output is correct
3 Correct 1854 ms 2056276 KB Output is correct
4 Correct 4416 ms 2097152 KB Output is correct
5 Correct 4133 ms 2090644 KB Output is correct
6 Correct 3157 ms 2081732 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3721 ms 2080736 KB Output is correct
2 Correct 4157 ms 2079768 KB Output is correct
3 Correct 1854 ms 2056276 KB Output is correct
4 Correct 4416 ms 2097152 KB Output is correct
5 Correct 4133 ms 2090644 KB Output is correct
6 Correct 3157 ms 2081732 KB Output is correct
7 Correct 3720 ms 2067416 KB Output is correct
8 Correct 4291 ms 2064208 KB Output is correct
9 Correct 4291 ms 2068020 KB Output is correct
10 Correct 3209 ms 2056440 KB Output is correct
11 Correct 5914 ms 2097152 KB Output is correct
12 Correct 7048 ms 2087776 KB Output is correct
13 Correct 7141 ms 2097152 KB Output is correct
14 Correct 668 ms 1978568 KB Output is correct
15 Correct 2051 ms 2055192 KB Output is correct
16 Correct 3775 ms 2068472 KB Output is correct
17 Correct 3477 ms 2072044 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 1975052 KB Output is correct
2 Correct 672 ms 1975080 KB Output is correct
3 Correct 669 ms 1975076 KB Output is correct
4 Correct 670 ms 1975360 KB Output is correct
5 Correct 713 ms 1975220 KB Output is correct
6 Correct 671 ms 1974936 KB Output is correct
7 Correct 3465 ms 2078468 KB Output is correct
8 Correct 3453 ms 2078256 KB Output is correct
9 Correct 3417 ms 2078548 KB Output is correct
10 Correct 2917 ms 2064920 KB Output is correct
11 Correct 7922 ms 2089212 KB Output is correct
12 Correct 6206 ms 2085264 KB Output is correct
13 Correct 3520 ms 2077344 KB Output is correct
14 Correct 3721 ms 2080736 KB Output is correct
15 Correct 4157 ms 2079768 KB Output is correct
16 Correct 1854 ms 2056276 KB Output is correct
17 Correct 4416 ms 2097152 KB Output is correct
18 Correct 4133 ms 2090644 KB Output is correct
19 Correct 3157 ms 2081732 KB Output is correct
20 Correct 3720 ms 2067416 KB Output is correct
21 Correct 4291 ms 2064208 KB Output is correct
22 Correct 4291 ms 2068020 KB Output is correct
23 Correct 3209 ms 2056440 KB Output is correct
24 Correct 5914 ms 2097152 KB Output is correct
25 Correct 7048 ms 2087776 KB Output is correct
26 Correct 7141 ms 2097152 KB Output is correct
27 Correct 668 ms 1978568 KB Output is correct
28 Correct 2051 ms 2055192 KB Output is correct
29 Correct 3775 ms 2068472 KB Output is correct
30 Correct 3477 ms 2072044 KB Output is correct
31 Correct 3482 ms 2076696 KB Output is correct
32 Correct 3802 ms 2072860 KB Output is correct
33 Correct 1758 ms 2066752 KB Output is correct
34 Correct 4367 ms 2090104 KB Output is correct
35 Correct 4390 ms 2092380 KB Output is correct
36 Correct 3085 ms 2068316 KB Output is correct
37 Runtime error 4686 ms 2097152 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -