oj.uz

Submission #926114

# Submission time Handle Problem Language Result Execution time Memory
926114 2024-02-12T15:05:58 Z manizare Sweeping (JOI20_sweeping) C++14
11 / 100
 6788 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 + 2e5 +  10 , maxp = 15e5 + 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 375 ms 1981168 KB Output is correct
2 Correct 366 ms 1980852 KB Output is correct
3 Correct 361 ms 1981012 KB Output is correct
4 Correct 377 ms 1981012 KB Output is correct
5 Correct 369 ms 1981464 KB Output is correct
6 Correct 359 ms 1981012 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3217 ms 2087248 KB Output is correct
2 Correct 3189 ms 2087208 KB Output is correct
3 Correct 3144 ms 2087448 KB Output is correct
4 Correct 2584 ms 2073960 KB Output is correct
5 Correct 6788 ms 2097152 KB Output is correct
6 Correct 5471 ms 2093932 KB Output is correct
7 Correct 3100 ms 2086324 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3290 ms 2088740 KB Output is correct
2 Correct 3619 ms 2088240 KB Output is correct
3 Correct 1421 ms 2064424 KB Output is correct
4 Runtime error 2504 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3290 ms 2088740 KB Output is correct
2 Correct 3619 ms 2088240 KB Output is correct
3 Correct 1421 ms 2064424 KB Output is correct
4 Runtime error 2504 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 1981168 KB Output is correct
2 Correct 366 ms 1980852 KB Output is correct
3 Correct 361 ms 1981012 KB Output is correct
4 Correct 377 ms 1981012 KB Output is correct
5 Correct 369 ms 1981464 KB Output is correct
6 Correct 359 ms 1981012 KB Output is correct
7 Correct 3217 ms 2087248 KB Output is correct
8 Correct 3189 ms 2087208 KB Output is correct
9 Correct 3144 ms 2087448 KB Output is correct
10 Correct 2584 ms 2073960 KB Output is correct
11 Correct 6788 ms 2097152 KB Output is correct
12 Correct 5471 ms 2093932 KB Output is correct
13 Correct 3100 ms 2086324 KB Output is correct
14 Correct 3290 ms 2088740 KB Output is correct
15 Correct 3619 ms 2088240 KB Output is correct
16 Correct 1421 ms 2064424 KB Output is correct
17 Runtime error 2504 ms 2097152 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -