oj.uz

Submission #926103

# Submission time Handle Problem Language Result Execution time Memory
926103 2024-02-12T14:59:10 Z manizare Sweeping (JOI20_sweeping) C++17
22 / 100
 7421 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 727 ms 1973584 KB Output is correct
2 Correct 966 ms 1974812 KB Output is correct
3 Correct 820 ms 1975252 KB Output is correct
4 Correct 776 ms 1974984 KB Output is correct
5 Correct 774 ms 1975380 KB Output is correct
6 Correct 788 ms 1975044 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3856 ms 2074720 KB Output is correct
2 Correct 3972 ms 2078948 KB Output is correct
3 Correct 3920 ms 2079712 KB Output is correct
4 Correct 3354 ms 2068800 KB Output is correct
5 Correct 7421 ms 2094116 KB Output is correct
6 Correct 6267 ms 2085144 KB Output is correct
7 Correct 3671 ms 2077160 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4140 ms 2080932 KB Output is correct
2 Correct 4273 ms 2079104 KB Output is correct
3 Correct 2104 ms 2056252 KB Output is correct
4 Correct 4216 ms 2097152 KB Output is correct
5 Correct 3851 ms 2089592 KB Output is correct
6 Correct 3374 ms 2081832 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4140 ms 2080932 KB Output is correct
2 Correct 4273 ms 2079104 KB Output is correct
3 Correct 2104 ms 2056252 KB Output is correct
4 Correct 4216 ms 2097152 KB Output is correct
5 Correct 3851 ms 2089592 KB Output is correct
6 Correct 3374 ms 2081832 KB Output is correct
7 Correct 4169 ms 2067684 KB Output is correct
8 Correct 4422 ms 2069996 KB Output is correct
9 Correct 4096 ms 2060668 KB Output is correct
10 Correct 3218 ms 2056776 KB Output is correct
11 Runtime error 5423 ms 2097152 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 1973584 KB Output is correct
2 Correct 966 ms 1974812 KB Output is correct
3 Correct 820 ms 1975252 KB Output is correct
4 Correct 776 ms 1974984 KB Output is correct
5 Correct 774 ms 1975380 KB Output is correct
6 Correct 788 ms 1975044 KB Output is correct
7 Correct 3856 ms 2074720 KB Output is correct
8 Correct 3972 ms 2078948 KB Output is correct
9 Correct 3920 ms 2079712 KB Output is correct
10 Correct 3354 ms 2068800 KB Output is correct
11 Correct 7421 ms 2094116 KB Output is correct
12 Correct 6267 ms 2085144 KB Output is correct
13 Correct 3671 ms 2077160 KB Output is correct
14 Correct 4140 ms 2080932 KB Output is correct
15 Correct 4273 ms 2079104 KB Output is correct
16 Correct 2104 ms 2056252 KB Output is correct
17 Correct 4216 ms 2097152 KB Output is correct
18 Correct 3851 ms 2089592 KB Output is correct
19 Correct 3374 ms 2081832 KB Output is correct
20 Correct 4169 ms 2067684 KB Output is correct
21 Correct 4422 ms 2069996 KB Output is correct
22 Correct 4096 ms 2060668 KB Output is correct
23 Correct 3218 ms 2056776 KB Output is correct
24 Runtime error 5423 ms 2097152 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -