oj.uz

Submission #926106

# Submission time Handle Problem Language Result Execution time Memory
926106 2024-02-12T15:01:43 Z manizare Sweeping (JOI20_sweeping) C++14
75 / 100
 6305 ms 2097152 KB 
#include <bits/stdc++.h>
#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 487 ms 1981008 KB Output is correct
2 Correct 362 ms 1980996 KB Output is correct
3 Correct 361 ms 1981268 KB Output is correct
4 Correct 379 ms 1981476 KB Output is correct
5 Correct 360 ms 1981412 KB Output is correct
6 Correct 359 ms 1981032 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3246 ms 2085108 KB Output is correct
2 Correct 3190 ms 2085484 KB Output is correct
3 Correct 3186 ms 2085072 KB Output is correct
4 Correct 2628 ms 2072084 KB Output is correct
5 Correct 6305 ms 2097152 KB Output is correct
6 Correct 5539 ms 2091900 KB Output is correct
7 Correct 3027 ms 2084336 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3277 ms 2085928 KB Output is correct
2 Correct 3532 ms 2085784 KB Output is correct
3 Correct 1396 ms 2062508 KB Output is correct
4 Correct 3833 ms 2097152 KB Output is correct
5 Correct 3417 ms 2092924 KB Output is correct
6 Correct 2713 ms 2086992 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3277 ms 2085928 KB Output is correct
2 Correct 3532 ms 2085784 KB Output is correct
3 Correct 1396 ms 2062508 KB Output is correct
4 Correct 3833 ms 2097152 KB Output is correct
5 Correct 3417 ms 2092924 KB Output is correct
6 Correct 2713 ms 2086992 KB Output is correct
7 Correct 3582 ms 2072980 KB Output is correct
8 Correct 3439 ms 2075120 KB Output is correct
9 Correct 3540 ms 2070828 KB Output is correct
10 Correct 2855 ms 2047812 KB Output is correct
11 Correct 5723 ms 2097152 KB Output is correct
12 Correct 6187 ms 2092660 KB Output is correct
13 Correct 5673 ms 2097152 KB Output is correct
14 Correct 456 ms 1984592 KB Output is correct
15 Correct 1387 ms 2059388 KB Output is correct
16 Correct 3064 ms 2074344 KB Output is correct
17 Correct 3145 ms 2076304 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 1981008 KB Output is correct
2 Correct 362 ms 1980996 KB Output is correct
3 Correct 361 ms 1981268 KB Output is correct
4 Correct 379 ms 1981476 KB Output is correct
5 Correct 360 ms 1981412 KB Output is correct
6 Correct 359 ms 1981032 KB Output is correct
7 Correct 3246 ms 2085108 KB Output is correct
8 Correct 3190 ms 2085484 KB Output is correct
9 Correct 3186 ms 2085072 KB Output is correct
10 Correct 2628 ms 2072084 KB Output is correct
11 Correct 6305 ms 2097152 KB Output is correct
12 Correct 5539 ms 2091900 KB Output is correct
13 Correct 3027 ms 2084336 KB Output is correct
14 Correct 3277 ms 2085928 KB Output is correct
15 Correct 3532 ms 2085784 KB Output is correct
16 Correct 1396 ms 2062508 KB Output is correct
17 Correct 3833 ms 2097152 KB Output is correct
18 Correct 3417 ms 2092924 KB Output is correct
19 Correct 2713 ms 2086992 KB Output is correct
20 Correct 3582 ms 2072980 KB Output is correct
21 Correct 3439 ms 2075120 KB Output is correct
22 Correct 3540 ms 2070828 KB Output is correct
23 Correct 2855 ms 2047812 KB Output is correct
24 Correct 5723 ms 2097152 KB Output is correct
25 Correct 6187 ms 2092660 KB Output is correct
26 Correct 5673 ms 2097152 KB Output is correct
27 Correct 456 ms 1984592 KB Output is correct
28 Correct 1387 ms 2059388 KB Output is correct
29 Correct 3064 ms 2074344 KB Output is correct
30 Correct 3145 ms 2076304 KB Output is correct
31 Correct 3157 ms 2093544 KB Output is correct
32 Correct 3511 ms 2085004 KB Output is correct
33 Correct 1612 ms 2076156 KB Output is correct
34 Correct 4118 ms 2097152 KB Output is correct
35 Correct 4033 ms 2097152 KB Output is correct
36 Correct 2812 ms 2072296 KB Output is correct
37 Runtime error 4421 ms 2097152 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -