oj.uz

Submission #926138

# Submission time Handle Problem Language Result Execution time Memory
926138 2024-02-12T15:22:06 Z manizare Sweeping (JOI20_sweeping) C++14
100 / 100
 7514 ms 1637220 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 = 12e6 +  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 888 ms 1481592 KB Output is correct
2 Correct 637 ms 1487428 KB Output is correct
3 Correct 335 ms 1482524 KB Output is correct
4 Correct 390 ms 1482672 KB Output is correct
5 Correct 681 ms 1481624 KB Output is correct
6 Correct 287 ms 1482360 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4114 ms 1581984 KB Output is correct
2 Correct 3778 ms 1586720 KB Output is correct
3 Correct 3493 ms 1587844 KB Output is correct
4 Correct 3108 ms 1578180 KB Output is correct
5 Correct 7514 ms 1602496 KB Output is correct
6 Correct 6022 ms 1595296 KB Output is correct
7 Correct 3199 ms 1585984 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3547 ms 1584344 KB Output is correct
2 Correct 3722 ms 1594440 KB Output is correct
3 Correct 1465 ms 1564292 KB Output is correct
4 Correct 4067 ms 1620528 KB Output is correct
5 Correct 3745 ms 1598956 KB Output is correct
6 Correct 2846 ms 1589680 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3547 ms 1584344 KB Output is correct
2 Correct 3722 ms 1594440 KB Output is correct
3 Correct 1465 ms 1564292 KB Output is correct
4 Correct 4067 ms 1620528 KB Output is correct
5 Correct 3745 ms 1598956 KB Output is correct
6 Correct 2846 ms 1589680 KB Output is correct
7 Correct 3373 ms 1583200 KB Output is correct
8 Correct 3371 ms 1585356 KB Output is correct
9 Correct 3330 ms 1583492 KB Output is correct
10 Correct 2508 ms 1572228 KB Output is correct
11 Correct 5337 ms 1628764 KB Output is correct
12 Correct 6275 ms 1604272 KB Output is correct
13 Correct 5883 ms 1603400 KB Output is correct
14 Correct 353 ms 1488304 KB Output is correct
15 Correct 1464 ms 1554948 KB Output is correct
16 Correct 3047 ms 1564736 KB Output is correct
17 Correct 3114 ms 1567240 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 888 ms 1481592 KB Output is correct
2 Correct 637 ms 1487428 KB Output is correct
3 Correct 335 ms 1482524 KB Output is correct
4 Correct 390 ms 1482672 KB Output is correct
5 Correct 681 ms 1481624 KB Output is correct
6 Correct 287 ms 1482360 KB Output is correct
7 Correct 4114 ms 1581984 KB Output is correct
8 Correct 3778 ms 1586720 KB Output is correct
9 Correct 3493 ms 1587844 KB Output is correct
10 Correct 3108 ms 1578180 KB Output is correct
11 Correct 7514 ms 1602496 KB Output is correct
12 Correct 6022 ms 1595296 KB Output is correct
13 Correct 3199 ms 1585984 KB Output is correct
14 Correct 3547 ms 1584344 KB Output is correct
15 Correct 3722 ms 1594440 KB Output is correct
16 Correct 1465 ms 1564292 KB Output is correct
17 Correct 4067 ms 1620528 KB Output is correct
18 Correct 3745 ms 1598956 KB Output is correct
19 Correct 2846 ms 1589680 KB Output is correct
20 Correct 3373 ms 1583200 KB Output is correct
21 Correct 3371 ms 1585356 KB Output is correct
22 Correct 3330 ms 1583492 KB Output is correct
23 Correct 2508 ms 1572228 KB Output is correct
24 Correct 5337 ms 1628764 KB Output is correct
25 Correct 6275 ms 1604272 KB Output is correct
26 Correct 5883 ms 1603400 KB Output is correct
27 Correct 353 ms 1488304 KB Output is correct
28 Correct 1464 ms 1554948 KB Output is correct
29 Correct 3047 ms 1564736 KB Output is correct
30 Correct 3114 ms 1567240 KB Output is correct
31 Correct 3101 ms 1581660 KB Output is correct
32 Correct 3608 ms 1572592 KB Output is correct
33 Correct 1515 ms 1562736 KB Output is correct
34 Correct 4059 ms 1590496 KB Output is correct
35 Correct 3932 ms 1587772 KB Output is correct
36 Correct 2749 ms 1559724 KB Output is correct
37 Correct 7234 ms 1637220 KB Output is correct
38 Correct 6460 ms 1609524 KB Output is correct
39 Correct 5697 ms 1609292 KB Output is correct
40 Correct 3121 ms 1575676 KB Output is correct