oj.uz

Submission #488318

# Submission time Handle Problem Language Result Execution time Memory
488318 2021-11-18T14:19:21 Z i_am_noob Port Facility (JOI17_port_facility) C++17
100 / 100
 933 ms 206716 KB 
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#include<x86intrin.h>
#include<immintrin.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
//#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

inline char readchar(){
    const int maxn=1000000;
    static char buf[maxn],*p=buf,*q=buf;
    if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF;
    else return *p++;
}
inline int readint(){
    int c=readchar(),x=0,neg=0;
    while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar();
    if(c=='-') neg=1,c=readchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar();
    return neg?-x:x;
}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=1000005;
//i_am_noob
#define v8si __attribute__ (( vector_size(32) )) signed

int val[maxn*8];

void pull(int k){val[k]=max(val[k<<1],val[k<<1|1]);}

void modify(int k, int l, int r, int p, int x){
    if(l==r){
        val[k]=x;
        return;
    }
    int mid=l+r>>1;
    if(p<=mid) modify(k<<1,l,mid,p,x);
    else modify(k<<1|1,mid+1,r,p,x);
    pull(k);
}

int query(int k, int l, int r, int ql, int qr){
    if(l>qr||r<ql) return -inf;
    if(ql<=l&&qr>=r) return val[k];
    int mid=l+r>>1;
    return max(query(k<<1,l,mid,ql,qr),query(k<<1|1,mid+1,r,ql,qr));
}

int par[maxn*2];
bool same[maxn*2];
vector<int> child[maxn*2];

int Find(int x){return par[x]==x?x:par[x]=Find(par[x]);}
void Union(int x, int y){
    bug(x,y);
    if(sz(child[Find(x)])<sz(child[Find(y)])) swap(x,y);
    int a=Find(x),b=Find(y);
    if(a==b){
        bug(x,y,same[x],same[y]);
        if(!(same[x]^same[y])){
            cout << "0\n";
            exit(0);
        }
        return;
    }
    if(!(same[x]^same[y])){
        for(auto i: child[b]) same[i]^=1;
    }
    for(auto i: child[b]) child[a].pb(i);
    bug(a);
    for(auto i: child[a]) bug(i,same[i]);
    child[b].clear();
    par[b]=a;
}

int n,a[maxn*2];

void orzck(){
    rep(maxn*8) val[i]=-inf;
    rep(maxn*2) par[i]=i,child[i].pb(i),same[i]=1;
    n=readint();
    rep(n){
        int x,y;
        x=readint(),y=readint();
        x--,y--;
        a[x]=y,a[y]=x;
    }
    rep(2*n) if(a[i]<i){
        int x=query(1,0,2*n-1,0,a[i]-1);
        if(x<a[i]){
            modify(1,0,2*n-1,a[i],i);
            continue;
        }
        Union(a[x],a[i]);
        modify(1,0,2*n-1,a[x],-inf);
        while(1){
            int y=query(1,0,2*n-1,0,a[i]-1);
            if(y<a[i]) break;
            Union(a[y],a[i]);
            modify(1,0,2*n-1,a[y],-inf);
        }
        modify(1,0,2*n-1,a[x],x);
        modify(1,0,2*n-1,a[i],i);
    }
    set<int> st;
    rep(2*n) if(a[i]>i) st.insert(Find(i));
    int res=1;
    rep(sz(st)) res=res*2%MOD;
    cout << res << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    cout << fixed << setprecision(15);
    orzck();
    return 0;
}

Compilation message

port_facility.cpp: In function 'void modify(int, int, int, int, int)':
port_facility.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid=l+r>>1;
      |             ~^~
port_facility.cpp: In function 'int query(int, int, int, int, int)':
port_facility.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid=l+r>>1;
      |             ~^~
port_facility.cpp: In function 'void Union(int, int)':
port_facility.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define bug(...) 826
      |                  ^~~
port_facility.cpp:81:5: note: in expansion of macro 'bug'
   81 |     bug(x,y);
      |     ^~~
port_facility.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define bug(...) 826
      |                  ^~~
port_facility.cpp:85:9: note: in expansion of macro 'bug'
   85 |         bug(x,y,same[x],same[y]);
      |         ^~~
port_facility.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define bug(...) 826
      |                  ^~~
port_facility.cpp:96:5: note: in expansion of macro 'bug'
   96 |     bug(a);
      |     ^~~
port_facility.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define bug(...) 826
      |                  ^~~
port_facility.cpp:97:27: note: in expansion of macro 'bug'
   97 |     for(auto i: child[a]) bug(i,same[i]);
      |                           ^~~
port_facility.cpp:97:14: warning: unused variable 'i' [-Wunused-variable]
   97 |     for(auto i: child[a]) bug(i,same[i]);
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 150980 KB Output is correct
2 Correct 121 ms 150888 KB Output is correct
3 Correct 122 ms 151000 KB Output is correct
4 Correct 127 ms 150892 KB Output is correct
5 Correct 121 ms 150912 KB Output is correct
6 Correct 122 ms 150916 KB Output is correct
7 Correct 124 ms 150988 KB Output is correct
8 Correct 122 ms 150964 KB Output is correct
9 Correct 127 ms 150932 KB Output is correct
10 Correct 122 ms 150936 KB Output is correct
11 Correct 123 ms 150980 KB Output is correct
12 Correct 122 ms 150908 KB Output is correct
13 Correct 122 ms 150924 KB Output is correct
14 Correct 129 ms 150992 KB Output is correct
15 Correct 122 ms 150948 KB Output is correct
16 Correct 127 ms 150964 KB Output is correct
17 Correct 122 ms 150996 KB Output is correct
18 Correct 120 ms 150992 KB Output is correct
19 Correct 128 ms 151016 KB Output is correct
20 Correct 127 ms 150976 KB Output is correct
21 Correct 121 ms 150960 KB Output is correct
22 Correct 121 ms 150916 KB Output is correct
23 Correct 124 ms 151088 KB Output is correct
24 Correct 122 ms 150984 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 150980 KB Output is correct
2 Correct 121 ms 150888 KB Output is correct
3 Correct 122 ms 151000 KB Output is correct
4 Correct 127 ms 150892 KB Output is correct
5 Correct 121 ms 150912 KB Output is correct
6 Correct 122 ms 150916 KB Output is correct
7 Correct 124 ms 150988 KB Output is correct
8 Correct 122 ms 150964 KB Output is correct
9 Correct 127 ms 150932 KB Output is correct
10 Correct 122 ms 150936 KB Output is correct
11 Correct 123 ms 150980 KB Output is correct
12 Correct 122 ms 150908 KB Output is correct
13 Correct 122 ms 150924 KB Output is correct
14 Correct 129 ms 150992 KB Output is correct
15 Correct 122 ms 150948 KB Output is correct
16 Correct 127 ms 150964 KB Output is correct
17 Correct 122 ms 150996 KB Output is correct
18 Correct 120 ms 150992 KB Output is correct
19 Correct 128 ms 151016 KB Output is correct
20 Correct 127 ms 150976 KB Output is correct
21 Correct 121 ms 150960 KB Output is correct
22 Correct 121 ms 150916 KB Output is correct
23 Correct 124 ms 151088 KB Output is correct
24 Correct 122 ms 150984 KB Output is correct
25 Correct 124 ms 150968 KB Output is correct
26 Correct 122 ms 150980 KB Output is correct
27 Correct 123 ms 151108 KB Output is correct
28 Correct 128 ms 151028 KB Output is correct
29 Correct 124 ms 150984 KB Output is correct
30 Correct 123 ms 150956 KB Output is correct
31 Correct 123 ms 150980 KB Output is correct
32 Correct 124 ms 150996 KB Output is correct
33 Correct 124 ms 151020 KB Output is correct
34 Correct 123 ms 150928 KB Output is correct
35 Correct 123 ms 150992 KB Output is correct
36 Correct 122 ms 151108 KB Output is correct
37 Correct 122 ms 150980 KB Output is correct
38 Correct 126 ms 150984 KB Output is correct
39 Correct 125 ms 151056 KB Output is correct
40 Correct 122 ms 151068 KB Output is correct
41 Correct 124 ms 151036 KB Output is correct
42 Correct 125 ms 151016 KB Output is correct
43 Correct 124 ms 151108 KB Output is correct
44 Correct 122 ms 151008 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 150980 KB Output is correct
2 Correct 121 ms 150888 KB Output is correct
3 Correct 122 ms 151000 KB Output is correct
4 Correct 127 ms 150892 KB Output is correct
5 Correct 121 ms 150912 KB Output is correct
6 Correct 122 ms 150916 KB Output is correct
7 Correct 124 ms 150988 KB Output is correct
8 Correct 122 ms 150964 KB Output is correct
9 Correct 127 ms 150932 KB Output is correct
10 Correct 122 ms 150936 KB Output is correct
11 Correct 123 ms 150980 KB Output is correct
12 Correct 122 ms 150908 KB Output is correct
13 Correct 122 ms 150924 KB Output is correct
14 Correct 129 ms 150992 KB Output is correct
15 Correct 122 ms 150948 KB Output is correct
16 Correct 127 ms 150964 KB Output is correct
17 Correct 122 ms 150996 KB Output is correct
18 Correct 120 ms 150992 KB Output is correct
19 Correct 128 ms 151016 KB Output is correct
20 Correct 127 ms 150976 KB Output is correct
21 Correct 121 ms 150960 KB Output is correct
22 Correct 121 ms 150916 KB Output is correct
23 Correct 124 ms 151088 KB Output is correct
24 Correct 122 ms 150984 KB Output is correct
25 Correct 124 ms 150968 KB Output is correct
26 Correct 122 ms 150980 KB Output is correct
27 Correct 123 ms 151108 KB Output is correct
28 Correct 128 ms 151028 KB Output is correct
29 Correct 124 ms 150984 KB Output is correct
30 Correct 123 ms 150956 KB Output is correct
31 Correct 123 ms 150980 KB Output is correct
32 Correct 124 ms 150996 KB Output is correct
33 Correct 124 ms 151020 KB Output is correct
34 Correct 123 ms 150928 KB Output is correct
35 Correct 123 ms 150992 KB Output is correct
36 Correct 122 ms 151108 KB Output is correct
37 Correct 122 ms 150980 KB Output is correct
38 Correct 126 ms 150984 KB Output is correct
39 Correct 125 ms 151056 KB Output is correct
40 Correct 122 ms 151068 KB Output is correct
41 Correct 124 ms 151036 KB Output is correct
42 Correct 125 ms 151016 KB Output is correct
43 Correct 124 ms 151108 KB Output is correct
44 Correct 122 ms 151008 KB Output is correct
45 Correct 205 ms 154180 KB Output is correct
46 Correct 236 ms 154260 KB Output is correct
47 Correct 207 ms 154296 KB Output is correct
48 Correct 209 ms 154252 KB Output is correct
49 Correct 205 ms 154304 KB Output is correct
50 Correct 172 ms 153204 KB Output is correct
51 Correct 184 ms 152808 KB Output is correct
52 Correct 165 ms 157368 KB Output is correct
53 Correct 191 ms 157456 KB Output is correct
54 Correct 127 ms 152628 KB Output is correct
55 Correct 129 ms 152644 KB Output is correct
56 Correct 127 ms 152624 KB Output is correct
57 Correct 183 ms 155076 KB Output is correct
58 Correct 188 ms 157344 KB Output is correct
59 Correct 183 ms 156996 KB Output is correct
60 Correct 179 ms 155552 KB Output is correct
61 Correct 198 ms 154624 KB Output is correct
62 Correct 156 ms 152708 KB Output is correct
63 Correct 156 ms 152876 KB Output is correct
64 Correct 167 ms 153092 KB Output is correct
65 Correct 131 ms 152680 KB Output is correct
66 Correct 128 ms 152656 KB Output is correct
67 Correct 174 ms 153372 KB Output is correct
68 Correct 176 ms 153360 KB Output is correct
69 Correct 180 ms 153380 KB Output is correct
70 Correct 176 ms 153364 KB Output is correct
71 Correct 170 ms 153408 KB Output is correct
72 Correct 170 ms 153308 KB Output is correct
73 Correct 171 ms 153412 KB Output is correct
74 Correct 173 ms 153388 KB Output is correct
75 Correct 176 ms 153320 KB Output is correct
76 Correct 196 ms 153300 KB Output is correct
77 Correct 182 ms 153340 KB Output is correct
78 Correct 186 ms 154176 KB Output is correct
79 Correct 205 ms 154196 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 150980 KB Output is correct
2 Correct 121 ms 150888 KB Output is correct
3 Correct 122 ms 151000 KB Output is correct
4 Correct 127 ms 150892 KB Output is correct
5 Correct 121 ms 150912 KB Output is correct
6 Correct 122 ms 150916 KB Output is correct
7 Correct 124 ms 150988 KB Output is correct
8 Correct 122 ms 150964 KB Output is correct
9 Correct 127 ms 150932 KB Output is correct
10 Correct 122 ms 150936 KB Output is correct
11 Correct 123 ms 150980 KB Output is correct
12 Correct 122 ms 150908 KB Output is correct
13 Correct 122 ms 150924 KB Output is correct
14 Correct 129 ms 150992 KB Output is correct
15 Correct 122 ms 150948 KB Output is correct
16 Correct 127 ms 150964 KB Output is correct
17 Correct 122 ms 150996 KB Output is correct
18 Correct 120 ms 150992 KB Output is correct
19 Correct 128 ms 151016 KB Output is correct
20 Correct 127 ms 150976 KB Output is correct
21 Correct 121 ms 150960 KB Output is correct
22 Correct 121 ms 150916 KB Output is correct
23 Correct 124 ms 151088 KB Output is correct
24 Correct 122 ms 150984 KB Output is correct
25 Correct 124 ms 150968 KB Output is correct
26 Correct 122 ms 150980 KB Output is correct
27 Correct 123 ms 151108 KB Output is correct
28 Correct 128 ms 151028 KB Output is correct
29 Correct 124 ms 150984 KB Output is correct
30 Correct 123 ms 150956 KB Output is correct
31 Correct 123 ms 150980 KB Output is correct
32 Correct 124 ms 150996 KB Output is correct
33 Correct 124 ms 151020 KB Output is correct
34 Correct 123 ms 150928 KB Output is correct
35 Correct 123 ms 150992 KB Output is correct
36 Correct 122 ms 151108 KB Output is correct
37 Correct 122 ms 150980 KB Output is correct
38 Correct 126 ms 150984 KB Output is correct
39 Correct 125 ms 151056 KB Output is correct
40 Correct 122 ms 151068 KB Output is correct
41 Correct 124 ms 151036 KB Output is correct
42 Correct 125 ms 151016 KB Output is correct
43 Correct 124 ms 151108 KB Output is correct
44 Correct 122 ms 151008 KB Output is correct
45 Correct 205 ms 154180 KB Output is correct
46 Correct 236 ms 154260 KB Output is correct
47 Correct 207 ms 154296 KB Output is correct
48 Correct 209 ms 154252 KB Output is correct
49 Correct 205 ms 154304 KB Output is correct
50 Correct 172 ms 153204 KB Output is correct
51 Correct 184 ms 152808 KB Output is correct
52 Correct 165 ms 157368 KB Output is correct
53 Correct 191 ms 157456 KB Output is correct
54 Correct 127 ms 152628 KB Output is correct
55 Correct 129 ms 152644 KB Output is correct
56 Correct 127 ms 152624 KB Output is correct
57 Correct 183 ms 155076 KB Output is correct
58 Correct 188 ms 157344 KB Output is correct
59 Correct 183 ms 156996 KB Output is correct
60 Correct 179 ms 155552 KB Output is correct
61 Correct 198 ms 154624 KB Output is correct
62 Correct 156 ms 152708 KB Output is correct
63 Correct 156 ms 152876 KB Output is correct
64 Correct 167 ms 153092 KB Output is correct
65 Correct 131 ms 152680 KB Output is correct
66 Correct 128 ms 152656 KB Output is correct
67 Correct 174 ms 153372 KB Output is correct
68 Correct 176 ms 153360 KB Output is correct
69 Correct 180 ms 153380 KB Output is correct
70 Correct 176 ms 153364 KB Output is correct
71 Correct 170 ms 153408 KB Output is correct
72 Correct 170 ms 153308 KB Output is correct
73 Correct 171 ms 153412 KB Output is correct
74 Correct 173 ms 153388 KB Output is correct
75 Correct 176 ms 153320 KB Output is correct
76 Correct 196 ms 153300 KB Output is correct
77 Correct 182 ms 153340 KB Output is correct
78 Correct 186 ms 154176 KB Output is correct
79 Correct 205 ms 154196 KB Output is correct
80 Correct 933 ms 174816 KB Output is correct
81 Correct 888 ms 175232 KB Output is correct
82 Correct 897 ms 175476 KB Output is correct
83 Correct 902 ms 175064 KB Output is correct
84 Correct 883 ms 174848 KB Output is correct
85 Correct 475 ms 161828 KB Output is correct
86 Correct 269 ms 160152 KB Output is correct
87 Correct 696 ms 206696 KB Output is correct
88 Correct 696 ms 206716 KB Output is correct
89 Correct 173 ms 159684 KB Output is correct
90 Correct 171 ms 159752 KB Output is correct
91 Correct 173 ms 159720 KB Output is correct
92 Correct 804 ms 183204 KB Output is correct
93 Correct 721 ms 206712 KB Output is correct
94 Correct 720 ms 196296 KB Output is correct
95 Correct 838 ms 180776 KB Output is correct
96 Correct 861 ms 176920 KB Output is correct
97 Correct 319 ms 159812 KB Output is correct
98 Correct 313 ms 160580 KB Output is correct
99 Correct 378 ms 161436 KB Output is correct
100 Correct 173 ms 159740 KB Output is correct
101 Correct 173 ms 159660 KB Output is correct
102 Correct 723 ms 164196 KB Output is correct
103 Correct 727 ms 164004 KB Output is correct
104 Correct 751 ms 164020 KB Output is correct
105 Correct 761 ms 164032 KB Output is correct
106 Correct 737 ms 163948 KB Output is correct
107 Correct 709 ms 164164 KB Output is correct
108 Correct 736 ms 163948 KB Output is correct
109 Correct 719 ms 163916 KB Output is correct
110 Correct 774 ms 163932 KB Output is correct
111 Correct 767 ms 163944 KB Output is correct
112 Correct 775 ms 164032 KB Output is correct
113 Correct 897 ms 175628 KB Output is correct
114 Correct 919 ms 175488 KB Output is correct