oj.uz

Submission #926094

# Submission time Handle Problem Language Result Execution time Memory
926094 2024-02-12T14:48:01 Z manizare Sweeping (JOI20_sweeping) C++14
75 / 100
 6985 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 ;
    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 ;
    if(r[p].cl ==0 ){
        r[p].cl = c ; c++;
    }
    if(r[p].cr ==0){
        r[p].cr = c ; c++ ;
    }
    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].cr , m1 , Y  , d/2); 
    }else{
        ADD(id , r[p].cl , 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(r[p].cl ==0 ){
        r[p].cl = c ; c++;
    }
    if(r[p].cr ==0){
        r[p].cr = c ; c++ ;
    }
    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].cl , X , m2 , d/2);
        else upd(l,t, r[p].cr , 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].cr , m1 , Y  , d/2); 
        else upd(l,t , r[p].cl , 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 965 ms 1975340 KB Output is correct
2 Correct 664 ms 1974868 KB Output is correct
3 Correct 662 ms 1975412 KB Output is correct
4 Correct 665 ms 1975124 KB Output is correct
5 Correct 665 ms 1975392 KB Output is correct
6 Correct 665 ms 1975044 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3944 ms 2066692 KB Output is correct
2 Correct 3758 ms 2072256 KB Output is correct
3 Correct 3745 ms 2075584 KB Output is correct
4 Correct 3053 ms 2065068 KB Output is correct
5 Correct 6985 ms 2083772 KB Output is correct
6 Correct 6111 ms 2083780 KB Output is correct
7 Correct 3740 ms 2067204 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3897 ms 2061668 KB Output is correct
2 Correct 4083 ms 2078500 KB Output is correct
3 Correct 1939 ms 2056176 KB Output is correct
4 Correct 4511 ms 2097152 KB Output is correct
5 Correct 4069 ms 2088456 KB Output is correct
6 Correct 3307 ms 2080812 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3897 ms 2061668 KB Output is correct
2 Correct 4083 ms 2078500 KB Output is correct
3 Correct 1939 ms 2056176 KB Output is correct
4 Correct 4511 ms 2097152 KB Output is correct
5 Correct 4069 ms 2088456 KB Output is correct
6 Correct 3307 ms 2080812 KB Output is correct
7 Correct 4248 ms 2067632 KB Output is correct
8 Correct 4229 ms 2066276 KB Output is correct
9 Correct 4190 ms 2062644 KB Output is correct
10 Correct 3044 ms 2054948 KB Output is correct
11 Correct 5801 ms 2097152 KB Output is correct
12 Correct 6901 ms 2087020 KB Output is correct
13 Correct 6356 ms 2097152 KB Output is correct
14 Correct 787 ms 1978480 KB Output is correct
15 Correct 1688 ms 2053704 KB Output is correct
16 Correct 3696 ms 2068852 KB Output is correct
17 Correct 3814 ms 2069512 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 1975340 KB Output is correct
2 Correct 664 ms 1974868 KB Output is correct
3 Correct 662 ms 1975412 KB Output is correct
4 Correct 665 ms 1975124 KB Output is correct
5 Correct 665 ms 1975392 KB Output is correct
6 Correct 665 ms 1975044 KB Output is correct
7 Correct 3944 ms 2066692 KB Output is correct
8 Correct 3758 ms 2072256 KB Output is correct
9 Correct 3745 ms 2075584 KB Output is correct
10 Correct 3053 ms 2065068 KB Output is correct
11 Correct 6985 ms 2083772 KB Output is correct
12 Correct 6111 ms 2083780 KB Output is correct
13 Correct 3740 ms 2067204 KB Output is correct
14 Correct 3897 ms 2061668 KB Output is correct
15 Correct 4083 ms 2078500 KB Output is correct
16 Correct 1939 ms 2056176 KB Output is correct
17 Correct 4511 ms 2097152 KB Output is correct
18 Correct 4069 ms 2088456 KB Output is correct
19 Correct 3307 ms 2080812 KB Output is correct
20 Correct 4248 ms 2067632 KB Output is correct
21 Correct 4229 ms 2066276 KB Output is correct
22 Correct 4190 ms 2062644 KB Output is correct
23 Correct 3044 ms 2054948 KB Output is correct
24 Correct 5801 ms 2097152 KB Output is correct
25 Correct 6901 ms 2087020 KB Output is correct
26 Correct 6356 ms 2097152 KB Output is correct
27 Correct 787 ms 1978480 KB Output is correct
28 Correct 1688 ms 2053704 KB Output is correct
29 Correct 3696 ms 2068852 KB Output is correct
30 Correct 3814 ms 2069512 KB Output is correct
31 Correct 3837 ms 2076076 KB Output is correct
32 Correct 4234 ms 2072860 KB Output is correct
33 Runtime error 4294 ms 2097152 KB Execution killed with signal 9
34 Halted 0 ms 0 KB -