oj.uz

Submission #926098

# Submission time Handle Problem Language Result Execution time Memory
926098 2024-02-12T14:54:08 Z manizare Sweeping (JOI20_sweeping) C++14
75 / 100
 6963 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 813 ms 1975148 KB Output is correct
2 Correct 652 ms 1974868 KB Output is correct
3 Correct 653 ms 1975232 KB Output is correct
4 Correct 660 ms 1975180 KB Output is correct
5 Correct 648 ms 1975380 KB Output is correct
6 Correct 641 ms 1974868 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3617 ms 2078592 KB Output is correct
2 Correct 3444 ms 2078396 KB Output is correct
3 Correct 3467 ms 2078424 KB Output is correct
4 Correct 2830 ms 2065064 KB Output is correct
5 Correct 6963 ms 2090432 KB Output is correct
6 Correct 5735 ms 2084220 KB Output is correct
7 Correct 3433 ms 2067920 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3546 ms 2061856 KB Output is correct
2 Correct 3953 ms 2079888 KB Output is correct
3 Correct 1713 ms 2056092 KB Output is correct
4 Correct 4183 ms 2097152 KB Output is correct
5 Correct 3813 ms 2088840 KB Output is correct
6 Correct 3118 ms 2080492 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3546 ms 2061856 KB Output is correct
2 Correct 3953 ms 2079888 KB Output is correct
3 Correct 1713 ms 2056092 KB Output is correct
4 Correct 4183 ms 2097152 KB Output is correct
5 Correct 3813 ms 2088840 KB Output is correct
6 Correct 3118 ms 2080492 KB Output is correct
7 Correct 3715 ms 2067436 KB Output is correct
8 Correct 3939 ms 2066476 KB Output is correct
9 Correct 3710 ms 2063980 KB Output is correct
10 Correct 2889 ms 2055560 KB Output is correct
11 Correct 5631 ms 2097152 KB Output is correct
12 Correct 6646 ms 2087284 KB Output is correct
13 Correct 6329 ms 2097152 KB Output is correct
14 Correct 797 ms 1978812 KB Output is correct
15 Correct 1734 ms 2054016 KB Output is correct
16 Correct 3331 ms 2068512 KB Output is correct
17 Correct 3484 ms 2069504 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 1975148 KB Output is correct
2 Correct 652 ms 1974868 KB Output is correct
3 Correct 653 ms 1975232 KB Output is correct
4 Correct 660 ms 1975180 KB Output is correct
5 Correct 648 ms 1975380 KB Output is correct
6 Correct 641 ms 1974868 KB Output is correct
7 Correct 3617 ms 2078592 KB Output is correct
8 Correct 3444 ms 2078396 KB Output is correct
9 Correct 3467 ms 2078424 KB Output is correct
10 Correct 2830 ms 2065064 KB Output is correct
11 Correct 6963 ms 2090432 KB Output is correct
12 Correct 5735 ms 2084220 KB Output is correct
13 Correct 3433 ms 2067920 KB Output is correct
14 Correct 3546 ms 2061856 KB Output is correct
15 Correct 3953 ms 2079888 KB Output is correct
16 Correct 1713 ms 2056092 KB Output is correct
17 Correct 4183 ms 2097152 KB Output is correct
18 Correct 3813 ms 2088840 KB Output is correct
19 Correct 3118 ms 2080492 KB Output is correct
20 Correct 3715 ms 2067436 KB Output is correct
21 Correct 3939 ms 2066476 KB Output is correct
22 Correct 3710 ms 2063980 KB Output is correct
23 Correct 2889 ms 2055560 KB Output is correct
24 Correct 5631 ms 2097152 KB Output is correct
25 Correct 6646 ms 2087284 KB Output is correct
26 Correct 6329 ms 2097152 KB Output is correct
27 Correct 797 ms 1978812 KB Output is correct
28 Correct 1734 ms 2054016 KB Output is correct
29 Correct 3331 ms 2068512 KB Output is correct
30 Correct 3484 ms 2069504 KB Output is correct
31 Correct 3450 ms 2076136 KB Output is correct
32 Correct 3860 ms 2073684 KB Output is correct
33 Correct 1917 ms 2067000 KB Output is correct
34 Correct 4536 ms 2090320 KB Output is correct
35 Correct 4563 ms 2091848 KB Output is correct
36 Correct 3276 ms 2065768 KB Output is correct
37 Runtime error 5120 ms 2097152 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -