oj.uz

Submission #926121

# Submission time Handle Problem Language Result Execution time Memory
926121 2024-02-12T15:10:02 Z manizare Sweeping (JOI20_sweeping) C++14
75 / 100
 6417 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 ;
const int maxn = 16e6 +  1e4 , maxp = 15e5 + 10 ;
int n,m,q,x[maxp] ,y[maxp] ,p[2][maxp] , cnt = 2 , c = 2 ;
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 397 ms 1958532 KB Output is correct
2 Correct 355 ms 1958320 KB Output is correct
3 Correct 352 ms 1958596 KB Output is correct
4 Correct 360 ms 1958484 KB Output is correct
5 Correct 360 ms 1958996 KB Output is correct
6 Correct 352 ms 1958480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3182 ms 2054636 KB Output is correct
2 Correct 3152 ms 2050140 KB Output is correct
3 Correct 3071 ms 2049552 KB Output is correct
4 Correct 2672 ms 2031236 KB Output is correct
5 Correct 6417 ms 2073204 KB Output is correct
6 Correct 5525 ms 2066948 KB Output is correct
7 Correct 3084 ms 2058432 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3333 ms 2059532 KB Output is correct
2 Correct 3552 ms 2058472 KB Output is correct
3 Correct 1370 ms 2032684 KB Output is correct
4 Correct 3910 ms 2097152 KB Output is correct
5 Correct 3562 ms 2074912 KB Output is correct
6 Correct 2680 ms 2067528 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3333 ms 2059532 KB Output is correct
2 Correct 3552 ms 2058472 KB Output is correct
3 Correct 1370 ms 2032684 KB Output is correct
4 Correct 3910 ms 2097152 KB Output is correct
5 Correct 3562 ms 2074912 KB Output is correct
6 Correct 2680 ms 2067528 KB Output is correct
7 Correct 3390 ms 2053332 KB Output is correct
8 Correct 3498 ms 2055216 KB Output is correct
9 Correct 3646 ms 2053496 KB Output is correct
10 Correct 2576 ms 2041680 KB Output is correct
11 Correct 5230 ms 2097152 KB Output is correct
12 Correct 6294 ms 2074392 KB Output is correct
13 Correct 5812 ms 2092640 KB Output is correct
14 Correct 449 ms 1962364 KB Output is correct
15 Correct 1391 ms 2038996 KB Output is correct
16 Correct 3040 ms 2054340 KB Output is correct
17 Correct 3173 ms 2057040 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 1958532 KB Output is correct
2 Correct 355 ms 1958320 KB Output is correct
3 Correct 352 ms 1958596 KB Output is correct
4 Correct 360 ms 1958484 KB Output is correct
5 Correct 360 ms 1958996 KB Output is correct
6 Correct 352 ms 1958480 KB Output is correct
7 Correct 3182 ms 2054636 KB Output is correct
8 Correct 3152 ms 2050140 KB Output is correct
9 Correct 3071 ms 2049552 KB Output is correct
10 Correct 2672 ms 2031236 KB Output is correct
11 Correct 6417 ms 2073204 KB Output is correct
12 Correct 5525 ms 2066948 KB Output is correct
13 Correct 3084 ms 2058432 KB Output is correct
14 Correct 3333 ms 2059532 KB Output is correct
15 Correct 3552 ms 2058472 KB Output is correct
16 Correct 1370 ms 2032684 KB Output is correct
17 Correct 3910 ms 2097152 KB Output is correct
18 Correct 3562 ms 2074912 KB Output is correct
19 Correct 2680 ms 2067528 KB Output is correct
20 Correct 3390 ms 2053332 KB Output is correct
21 Correct 3498 ms 2055216 KB Output is correct
22 Correct 3646 ms 2053496 KB Output is correct
23 Correct 2576 ms 2041680 KB Output is correct
24 Correct 5230 ms 2097152 KB Output is correct
25 Correct 6294 ms 2074392 KB Output is correct
26 Correct 5812 ms 2092640 KB Output is correct
27 Correct 449 ms 1962364 KB Output is correct
28 Correct 1391 ms 2038996 KB Output is correct
29 Correct 3040 ms 2054340 KB Output is correct
30 Correct 3173 ms 2057040 KB Output is correct
31 Correct 3164 ms 2074508 KB Output is correct
32 Correct 3533 ms 2065184 KB Output is correct
33 Correct 1590 ms 2055628 KB Output is correct
34 Correct 4018 ms 2085612 KB Output is correct
35 Correct 4161 ms 2082164 KB Output is correct
36 Correct 2878 ms 2050620 KB Output is correct
37 Runtime error 4700 ms 2097152 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -