oj.uz

Submission #926135

# Submission time Handle Problem Language Result Execution time Memory
926135 2024-02-12T15:21:22 Z manizare Sweeping (JOI20_sweeping) C++14
100 / 100
 7927 ms 1893256 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#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 = 14e6 +  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 346 ms 1722588 KB Output is correct
2 Correct 588 ms 1716096 KB Output is correct
3 Correct 518 ms 1716552 KB Output is correct
4 Correct 564 ms 1716508 KB Output is correct
5 Correct 537 ms 1716776 KB Output is correct
6 Correct 508 ms 1716144 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3549 ms 1828224 KB Output is correct
2 Correct 3508 ms 1823320 KB Output is correct
3 Correct 3529 ms 1821928 KB Output is correct
4 Correct 2850 ms 1810308 KB Output is correct
5 Correct 7631 ms 1834672 KB Output is correct
6 Correct 6397 ms 1829212 KB Output is correct
7 Correct 3458 ms 1821936 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3451 ms 1823824 KB Output is correct
2 Correct 4061 ms 1813308 KB Output is correct
3 Correct 1678 ms 1805868 KB Output is correct
4 Correct 4290 ms 1844108 KB Output is correct
5 Correct 4379 ms 1832212 KB Output is correct
6 Correct 3420 ms 1822596 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3451 ms 1823824 KB Output is correct
2 Correct 4061 ms 1813308 KB Output is correct
3 Correct 1678 ms 1805868 KB Output is correct
4 Correct 4290 ms 1844108 KB Output is correct
5 Correct 4379 ms 1832212 KB Output is correct
6 Correct 3420 ms 1822596 KB Output is correct
7 Correct 4557 ms 1817236 KB Output is correct
8 Correct 4250 ms 1812544 KB Output is correct
9 Correct 4377 ms 1811552 KB Output is correct
10 Correct 3494 ms 1799624 KB Output is correct
11 Correct 6793 ms 1851088 KB Output is correct
12 Correct 7304 ms 1828672 KB Output is correct
13 Correct 7143 ms 1849544 KB Output is correct
14 Correct 795 ms 1719840 KB Output is correct
15 Correct 1794 ms 1802884 KB Output is correct
16 Correct 2921 ms 1818396 KB Output is correct
17 Correct 2999 ms 1820840 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 1722588 KB Output is correct
2 Correct 588 ms 1716096 KB Output is correct
3 Correct 518 ms 1716552 KB Output is correct
4 Correct 564 ms 1716508 KB Output is correct
5 Correct 537 ms 1716776 KB Output is correct
6 Correct 508 ms 1716144 KB Output is correct
7 Correct 3549 ms 1828224 KB Output is correct
8 Correct 3508 ms 1823320 KB Output is correct
9 Correct 3529 ms 1821928 KB Output is correct
10 Correct 2850 ms 1810308 KB Output is correct
11 Correct 7631 ms 1834672 KB Output is correct
12 Correct 6397 ms 1829212 KB Output is correct
13 Correct 3458 ms 1821936 KB Output is correct
14 Correct 3451 ms 1823824 KB Output is correct
15 Correct 4061 ms 1813308 KB Output is correct
16 Correct 1678 ms 1805868 KB Output is correct
17 Correct 4290 ms 1844108 KB Output is correct
18 Correct 4379 ms 1832212 KB Output is correct
19 Correct 3420 ms 1822596 KB Output is correct
20 Correct 4557 ms 1817236 KB Output is correct
21 Correct 4250 ms 1812544 KB Output is correct
22 Correct 4377 ms 1811552 KB Output is correct
23 Correct 3494 ms 1799624 KB Output is correct
24 Correct 6793 ms 1851088 KB Output is correct
25 Correct 7304 ms 1828672 KB Output is correct
26 Correct 7143 ms 1849544 KB Output is correct
27 Correct 795 ms 1719840 KB Output is correct
28 Correct 1794 ms 1802884 KB Output is correct
29 Correct 2921 ms 1818396 KB Output is correct
30 Correct 2999 ms 1820840 KB Output is correct
31 Correct 3186 ms 1838344 KB Output is correct
32 Correct 3502 ms 1829508 KB Output is correct
33 Correct 1454 ms 1819464 KB Output is correct
34 Correct 4059 ms 1855792 KB Output is correct
35 Correct 4049 ms 1853104 KB Output is correct
36 Correct 2921 ms 1815760 KB Output is correct
37 Correct 7927 ms 1893256 KB Output is correct
38 Correct 6766 ms 1866132 KB Output is correct
39 Correct 6265 ms 1865568 KB Output is correct
40 Correct 3173 ms 1832020 KB Output is correct