#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<int,int> ii;
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define RST(i,n) memset(i,n,sizeof i)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(),a.end()
#define X first
#define Y second
#define mkp make_pair
#define pb push_back
#define eb emplace_back
#define pob pop_back
#ifdef cold66
#define debug(...) do{\
fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<", ";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
_s<<"{";
for(It _it=_ita;_it!=_itb;_it++)
{
_s<<(_it==_ita?"":",")<<*_it;
}
_s<<"}";
return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // cold66
//}
template<class T> inline bool chkmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
const ll MAXn=1e6+5,MAXlg=__lg(MAXn)+2;
const ll MOD=1000000007;
const ll INF=0x3f3f3f3f;
int n;
ii d[MAXn];
int dl[MAXn*2],dr[MAXn*2];
ii mxseg[MAXn*4],mnseg[MAXn*4];
bitset<MAXn> vis;
bool col[MAXn];
int id[MAXn*2];
ll mul(ll a,ll b){
return a*b%MOD;
}
ll fpow(ll a,ll b){
ll ret = 1;
while (b) {
if (b&1) ret = mul(ret,a);
a = mul(a,a);
b >>= 1;
}
return ret;
}
void build(){
for (int i=2*n-1;i;i--) {
mnseg[i] = min(mnseg[i<<1],mnseg[i<<1|1]);
mxseg[i] = max(mxseg[i<<1],mxseg[i<<1|1]);
}
}
void mnins(int x,int val){
mnseg[x+2*n].X = val;
for (int i=x+2*n;i>1;i>>=1) {
mnseg[i>>1] = min(mnseg[i],mnseg[i^1]);
}
}
void mxins(int x,int val){
mxseg[x+2*n].X = val;
for (int i=x+2*n;i>1;i>>=1) {
mxseg[i>>1] = max(mxseg[i],mxseg[i^1]);
}
}
ii mnqr(int l,int r){
ii ret = ii(2*n,2*n);
for (l+=2*n,r+=2*n;l<r;l>>=1,r>>=1) {
if (l&1) ret = min(ret,mnseg[l++]);
if (r&1) ret = min(ret,mnseg[--r]);
}
return ret;
}
ii mxqr(int l,int r){
ii ret = ii(-1,-1);
for (l+=2*n,r+=2*n;l<r;l>>=1,r>>=1) {
if (l&1) ret = max(ret,mxseg[l++]);
if (r&1) ret = max(ret,mxseg[--r]);
}
return ret;
}
void gogo(int x){
queue<int> q;
q.push(x);
mxins(d[x].X,-1), mnins(d[x].Y,2*n);
while (SZ(q)) {
int cur = q.front();
q.pop();
vis[cur] = true;
int l = d[cur].X, r = d[cur].Y;
ii tmp = mxqr(l,r+1);
while (tmp.X > r) {
int nxt = id[tmp.Y];
col[nxt] = !col[cur];
int tl = d[nxt].X, tr = d[nxt].Y;
mxins(tl,-1), mnins(tr,2*n);
tmp = mxqr(l,r+1);
q.push(nxt);
}
tmp = mnqr(l,r+1);
while (tmp.X < l) {
int nxt = id[tmp.Y];
col[nxt] = !col[cur];
int tl = d[nxt].X, tr = d[nxt].Y;
mxins(tl,-1), mnins(tr,2*n);
tmp = mnqr(l,r+1);
q.push(nxt);
}
}
}
bool chk(){
vector<ii> port(2*n+1);
REP (i,n) {
port[d[i].X] = ii(i,col[i]);
port[d[i].Y] = ii(-i,col[i]);
}
vector<int> stk[2];
REP (i,2*n) {
if (port[i].X >= 0) {
stk[port[i].Y].eb(port[i].X);
}
else {
if (stk[port[i].Y].back() != -port[i].X) return false;
stk[port[i].Y].pob();
}
}
return true;
}
int main(){
IOS();
cin >> n;
REP (i,n) {
cin >> d[i].X >> d[i].Y;
d[i].X--, d[i].Y--;
}
sort(d,d+n);
REP (i,2*n) {
dl[i] = -1;
dr[i] = 2*n;
}
REP (i,n) {
id[d[i].X] = id[d[i].Y] = i;
dl[d[i].X] = d[i].Y;
dr[d[i].Y] = d[i].X;
}
REP (i,2*n) {
mxseg[i+2*n] = ii(dl[i],i);
mnseg[i+2*n] = ii(dr[i],i);
}
build();
ll ans = 0;
REP (i,n) {
if (!vis[i]) {
gogo(i);
ans++;
}
}
pary(col,col+n);
if (chk()) cout << fpow(2LL,ans) << endl;
else cout << 0 << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
380 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
380 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
380 KB |
Output is correct |
25 |
Correct |
6 ms |
632 KB |
Output is correct |
26 |
Correct |
7 ms |
632 KB |
Output is correct |
27 |
Correct |
7 ms |
632 KB |
Output is correct |
28 |
Correct |
6 ms |
632 KB |
Output is correct |
29 |
Correct |
7 ms |
632 KB |
Output is correct |
30 |
Correct |
7 ms |
632 KB |
Output is correct |
31 |
Correct |
7 ms |
632 KB |
Output is correct |
32 |
Correct |
6 ms |
632 KB |
Output is correct |
33 |
Correct |
7 ms |
636 KB |
Output is correct |
34 |
Correct |
7 ms |
632 KB |
Output is correct |
35 |
Correct |
7 ms |
632 KB |
Output is correct |
36 |
Correct |
6 ms |
632 KB |
Output is correct |
37 |
Correct |
6 ms |
632 KB |
Output is correct |
38 |
Correct |
6 ms |
632 KB |
Output is correct |
39 |
Correct |
6 ms |
632 KB |
Output is correct |
40 |
Correct |
7 ms |
636 KB |
Output is correct |
41 |
Correct |
6 ms |
632 KB |
Output is correct |
42 |
Correct |
6 ms |
632 KB |
Output is correct |
43 |
Correct |
6 ms |
632 KB |
Output is correct |
44 |
Correct |
6 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
380 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
380 KB |
Output is correct |
25 |
Correct |
6 ms |
632 KB |
Output is correct |
26 |
Correct |
7 ms |
632 KB |
Output is correct |
27 |
Correct |
7 ms |
632 KB |
Output is correct |
28 |
Correct |
6 ms |
632 KB |
Output is correct |
29 |
Correct |
7 ms |
632 KB |
Output is correct |
30 |
Correct |
7 ms |
632 KB |
Output is correct |
31 |
Correct |
7 ms |
632 KB |
Output is correct |
32 |
Correct |
6 ms |
632 KB |
Output is correct |
33 |
Correct |
7 ms |
636 KB |
Output is correct |
34 |
Correct |
7 ms |
632 KB |
Output is correct |
35 |
Correct |
7 ms |
632 KB |
Output is correct |
36 |
Correct |
6 ms |
632 KB |
Output is correct |
37 |
Correct |
6 ms |
632 KB |
Output is correct |
38 |
Correct |
6 ms |
632 KB |
Output is correct |
39 |
Correct |
6 ms |
632 KB |
Output is correct |
40 |
Correct |
7 ms |
636 KB |
Output is correct |
41 |
Correct |
6 ms |
632 KB |
Output is correct |
42 |
Correct |
6 ms |
632 KB |
Output is correct |
43 |
Correct |
6 ms |
632 KB |
Output is correct |
44 |
Correct |
6 ms |
632 KB |
Output is correct |
45 |
Correct |
105 ms |
11768 KB |
Output is correct |
46 |
Correct |
104 ms |
13048 KB |
Output is correct |
47 |
Correct |
108 ms |
13048 KB |
Output is correct |
48 |
Correct |
104 ms |
13048 KB |
Output is correct |
49 |
Correct |
123 ms |
13028 KB |
Output is correct |
50 |
Correct |
103 ms |
12920 KB |
Output is correct |
51 |
Correct |
103 ms |
13176 KB |
Output is correct |
52 |
Correct |
82 ms |
12600 KB |
Output is correct |
53 |
Correct |
96 ms |
13304 KB |
Output is correct |
54 |
Correct |
87 ms |
13488 KB |
Output is correct |
55 |
Correct |
83 ms |
13144 KB |
Output is correct |
56 |
Correct |
82 ms |
13144 KB |
Output is correct |
57 |
Correct |
72 ms |
12664 KB |
Output is correct |
58 |
Correct |
84 ms |
12664 KB |
Output is correct |
59 |
Correct |
96 ms |
13048 KB |
Output is correct |
60 |
Correct |
93 ms |
13048 KB |
Output is correct |
61 |
Correct |
99 ms |
13048 KB |
Output is correct |
62 |
Correct |
90 ms |
13048 KB |
Output is correct |
63 |
Correct |
94 ms |
12792 KB |
Output is correct |
64 |
Correct |
98 ms |
12792 KB |
Output is correct |
65 |
Correct |
131 ms |
13212 KB |
Output is correct |
66 |
Correct |
137 ms |
13204 KB |
Output is correct |
67 |
Correct |
90 ms |
13396 KB |
Output is correct |
68 |
Correct |
91 ms |
13312 KB |
Output is correct |
69 |
Correct |
90 ms |
13516 KB |
Output is correct |
70 |
Correct |
90 ms |
13524 KB |
Output is correct |
71 |
Correct |
84 ms |
13568 KB |
Output is correct |
72 |
Correct |
83 ms |
13396 KB |
Output is correct |
73 |
Correct |
85 ms |
13516 KB |
Output is correct |
74 |
Correct |
85 ms |
13696 KB |
Output is correct |
75 |
Correct |
65 ms |
12788 KB |
Output is correct |
76 |
Correct |
66 ms |
12792 KB |
Output is correct |
77 |
Correct |
66 ms |
12684 KB |
Output is correct |
78 |
Correct |
100 ms |
13048 KB |
Output is correct |
79 |
Correct |
102 ms |
13224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
6 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
380 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
380 KB |
Output is correct |
25 |
Correct |
6 ms |
632 KB |
Output is correct |
26 |
Correct |
7 ms |
632 KB |
Output is correct |
27 |
Correct |
7 ms |
632 KB |
Output is correct |
28 |
Correct |
6 ms |
632 KB |
Output is correct |
29 |
Correct |
7 ms |
632 KB |
Output is correct |
30 |
Correct |
7 ms |
632 KB |
Output is correct |
31 |
Correct |
7 ms |
632 KB |
Output is correct |
32 |
Correct |
6 ms |
632 KB |
Output is correct |
33 |
Correct |
7 ms |
636 KB |
Output is correct |
34 |
Correct |
7 ms |
632 KB |
Output is correct |
35 |
Correct |
7 ms |
632 KB |
Output is correct |
36 |
Correct |
6 ms |
632 KB |
Output is correct |
37 |
Correct |
6 ms |
632 KB |
Output is correct |
38 |
Correct |
6 ms |
632 KB |
Output is correct |
39 |
Correct |
6 ms |
632 KB |
Output is correct |
40 |
Correct |
7 ms |
636 KB |
Output is correct |
41 |
Correct |
6 ms |
632 KB |
Output is correct |
42 |
Correct |
6 ms |
632 KB |
Output is correct |
43 |
Correct |
6 ms |
632 KB |
Output is correct |
44 |
Correct |
6 ms |
632 KB |
Output is correct |
45 |
Correct |
105 ms |
11768 KB |
Output is correct |
46 |
Correct |
104 ms |
13048 KB |
Output is correct |
47 |
Correct |
108 ms |
13048 KB |
Output is correct |
48 |
Correct |
104 ms |
13048 KB |
Output is correct |
49 |
Correct |
123 ms |
13028 KB |
Output is correct |
50 |
Correct |
103 ms |
12920 KB |
Output is correct |
51 |
Correct |
103 ms |
13176 KB |
Output is correct |
52 |
Correct |
82 ms |
12600 KB |
Output is correct |
53 |
Correct |
96 ms |
13304 KB |
Output is correct |
54 |
Correct |
87 ms |
13488 KB |
Output is correct |
55 |
Correct |
83 ms |
13144 KB |
Output is correct |
56 |
Correct |
82 ms |
13144 KB |
Output is correct |
57 |
Correct |
72 ms |
12664 KB |
Output is correct |
58 |
Correct |
84 ms |
12664 KB |
Output is correct |
59 |
Correct |
96 ms |
13048 KB |
Output is correct |
60 |
Correct |
93 ms |
13048 KB |
Output is correct |
61 |
Correct |
99 ms |
13048 KB |
Output is correct |
62 |
Correct |
90 ms |
13048 KB |
Output is correct |
63 |
Correct |
94 ms |
12792 KB |
Output is correct |
64 |
Correct |
98 ms |
12792 KB |
Output is correct |
65 |
Correct |
131 ms |
13212 KB |
Output is correct |
66 |
Correct |
137 ms |
13204 KB |
Output is correct |
67 |
Correct |
90 ms |
13396 KB |
Output is correct |
68 |
Correct |
91 ms |
13312 KB |
Output is correct |
69 |
Correct |
90 ms |
13516 KB |
Output is correct |
70 |
Correct |
90 ms |
13524 KB |
Output is correct |
71 |
Correct |
84 ms |
13568 KB |
Output is correct |
72 |
Correct |
83 ms |
13396 KB |
Output is correct |
73 |
Correct |
85 ms |
13516 KB |
Output is correct |
74 |
Correct |
85 ms |
13696 KB |
Output is correct |
75 |
Correct |
65 ms |
12788 KB |
Output is correct |
76 |
Correct |
66 ms |
12792 KB |
Output is correct |
77 |
Correct |
66 ms |
12684 KB |
Output is correct |
78 |
Correct |
100 ms |
13048 KB |
Output is correct |
79 |
Correct |
102 ms |
13224 KB |
Output is correct |
80 |
Correct |
1029 ms |
127852 KB |
Output is correct |
81 |
Correct |
1048 ms |
127732 KB |
Output is correct |
82 |
Correct |
1041 ms |
128100 KB |
Output is correct |
83 |
Correct |
1020 ms |
127700 KB |
Output is correct |
84 |
Correct |
1044 ms |
127868 KB |
Output is correct |
85 |
Correct |
1016 ms |
127452 KB |
Output is correct |
86 |
Correct |
1016 ms |
127468 KB |
Output is correct |
87 |
Correct |
792 ms |
124664 KB |
Output is correct |
88 |
Correct |
1010 ms |
128876 KB |
Output is correct |
89 |
Correct |
843 ms |
130076 KB |
Output is correct |
90 |
Correct |
857 ms |
125544 KB |
Output is correct |
91 |
Correct |
853 ms |
125556 KB |
Output is correct |
92 |
Correct |
769 ms |
123512 KB |
Output is correct |
93 |
Correct |
824 ms |
122360 KB |
Output is correct |
94 |
Correct |
953 ms |
125284 KB |
Output is correct |
95 |
Correct |
986 ms |
125068 KB |
Output is correct |
96 |
Correct |
1016 ms |
125200 KB |
Output is correct |
97 |
Correct |
939 ms |
124308 KB |
Output is correct |
98 |
Correct |
991 ms |
124492 KB |
Output is correct |
99 |
Correct |
1018 ms |
124140 KB |
Output is correct |
100 |
Correct |
1911 ms |
125956 KB |
Output is correct |
101 |
Correct |
1834 ms |
128808 KB |
Output is correct |
102 |
Correct |
931 ms |
130724 KB |
Output is correct |
103 |
Correct |
935 ms |
130888 KB |
Output is correct |
104 |
Correct |
931 ms |
131456 KB |
Output is correct |
105 |
Correct |
926 ms |
131264 KB |
Output is correct |
106 |
Correct |
939 ms |
130752 KB |
Output is correct |
107 |
Correct |
891 ms |
130684 KB |
Output is correct |
108 |
Correct |
890 ms |
131204 KB |
Output is correct |
109 |
Correct |
903 ms |
131424 KB |
Output is correct |
110 |
Correct |
673 ms |
125572 KB |
Output is correct |
111 |
Correct |
690 ms |
125748 KB |
Output is correct |
112 |
Correct |
690 ms |
125684 KB |
Output is correct |
113 |
Correct |
1132 ms |
127680 KB |
Output is correct |
114 |
Correct |
1039 ms |
127996 KB |
Output is correct |