답안 #20495 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20495	2017-02-12T05:55:10 Z	안녕하세요 투어리스트입니다 진짜에요(#49, Namnamseo)	초음속철도 (OJUZ11_rail)	C++14	0 / 100	623 ms	44224 KB

rail

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back

pp data[200010];
int n;
vector<int> xp;

void in(){
	int p;
	read(p); xp.pb(1); xp.pb(p);
	read(n);
	for(int i=1; i<=n; ++i){
		int a, b; read(a, b);
		xp.pb(a); xp.pb(b); data[i]=pp{a, b};
	}
}

int xn;

void cc(){
	sort(all(xp));
	xp.erase(unique(all(xp)), xp.end());
	for(int i=1; i<=n; ++i){
		int a, b; tie(a, b) = data[i];
		a = lower_bound(all(xp), a) - xp.begin();
		b = lower_bound(all(xp), b) - xp.begin();
		data[i] = pp{a, b};
	}
	xn = xp.size();
}

const ll M=1'000'000'007;
const ll inv2=(M+1)/2;
ll dp[200010];
ll p2[400010];

auto rcmp = [](const pp& a, const pp& b){ return a.second < b.second; };

struct SEG {
	static const int T=524288;
	ll tsum[T<<1];
	ll tdp [T<<1];
	ll ttwo[T<<1];
	ll lazy[T<<1];
	void init(){
		for(auto& x:ttwo) x=1;
		for(auto& x:lazy) x=1;
	}
	void pd(int l, int r, int p){
		if(l==r || lazy[p]==1) return;
		for(int i=0; i<2; ++i){
			int x=p*2+i;
			tsum[x] = (tsum[x]*lazy[p])%M;
			ttwo[x] = (ttwo[x]*lazy[p])%M;
			lazy[x] = (lazy[x]*lazy[p])%M;
		}
		lazy[p]=1;
	}
	void divhalf(int l, int r, int ml=0, int mr=n, int p=1){
		pd(ml, mr, p);
		if(r<ml || mr<l) return;
		if(l<=ml && mr<=r){
			tsum[p] = (tsum[p]*inv2)%M;
			ttwo[p] = (ttwo[p]*inv2)%M;
			lazy[p] = inv2;
			return;
		}
		int mid=(ml+mr)/2;
		divhalf(l, r, ml, mid, p*2);
		divhalf(l, r, mid+1, mr, p*2+1);
		tsum[p]=(tsum[p*2]+tsum[p*2+1])%M;
	}
	ll rsum(int l, int r, int ml=0, int mr=n, int p=1){
		pd(ml, mr, p);
		if(r<ml || mr<l) return 0;
		if(l<=ml && mr<=r) return tsum[p];
		int mid=(ml+mr)/2;
		return rsum(l, r, ml, mid, p*2) + rsum(l, r, mid+1, mr, p*2+1);
	}
	void upd(int up, ll uv, int ml=0, int mr=n, int p=1){
		pd(ml, mr, p);
		if(up<ml || mr<up) return;
		if(ml==up && mr==up){
			tdp[p]=uv;
			tsum[p]=(tdp[p]*ttwo[p])%M;
			return;
		}
		int mid=(ml+mr)/2;
		upd(up, uv, ml, mid, p*2);
		upd(up, uv, mid+1, mr, p*2+1);
		tsum[p]=(tsum[p*2]+tsum[p*2+1])%M;
	}
} seg;

int main()
{
	//freopen("in", "r", stdin);
    in(); cc();
    
    p2[0]=1; for(int i=1; i<=400000; ++i) p2[i]=(p2[i-1]*2)%M;
    
    sort(data+1, data+n+1, rcmp);
    
    seg.init();
    dp[0]=1; seg.upd(0, 1);
    
    for(int i=1; i<=n; ++i){
		int a, b; tie(a, b) = data[i];
		int last = lower_bound(data, data+n+1, pp{0, a})-data-1;
		ll invdp = seg.rsum(0, last);
		invdp = (invdp * p2[i-1])%M;
		dp[i] = (p2[i-1]-invdp+M)%M;
		seg.divhalf(last+1, n);
		seg.upd(i, dp[i]);
    }
    
    ll ans=0;
    for(int i=1; i<=n; ++i) if(data[i].second == xn-1) ans = (ans+dp[i])%M;
    printf("%lld\n", ans);
    return 0;
}

Compilation message

rail.cpp: In function 'void read(int&)':
rail.cpp:5:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	41068 KB	Output is correct
2	Incorrect	6 ms	41068 KB	Output isn't correct
3	Correct	3 ms	41068 KB	Output is correct
4	Incorrect	0 ms	41068 KB	Output isn't correct
5	Correct	3 ms	41068 KB	Output is correct
6	Correct	3 ms	41068 KB	Output is correct
7	Incorrect	0 ms	41068 KB	Output isn't correct
8	Incorrect	0 ms	41068 KB	Output isn't correct
9	Correct	3 ms	41068 KB	Output is correct
10	Correct	6 ms	41068 KB	Output is correct
11	Incorrect	0 ms	41068 KB	Output isn't correct
12	Incorrect	0 ms	41068 KB	Output isn't correct
13	Correct	3 ms	41068 KB	Output is correct
14	Correct	9 ms	41068 KB	Output is correct
15	Incorrect	0 ms	41068 KB	Output isn't correct
16	Correct	3 ms	41068 KB	Output is correct
17	Correct	6 ms	41068 KB	Output is correct
18	Correct	6 ms	41068 KB	Output is correct

Subtask #2
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	41068 KB	Output is correct
2	Incorrect	6 ms	41068 KB	Output isn't correct
3	Correct	3 ms	41068 KB	Output is correct
4	Incorrect	0 ms	41068 KB	Output isn't correct
5	Correct	3 ms	41068 KB	Output is correct
6	Correct	3 ms	41068 KB	Output is correct
7	Incorrect	0 ms	41068 KB	Output isn't correct
8	Incorrect	0 ms	41068 KB	Output isn't correct
9	Correct	3 ms	41068 KB	Output is correct
10	Correct	6 ms	41068 KB	Output is correct
11	Incorrect	0 ms	41068 KB	Output isn't correct
12	Incorrect	0 ms	41068 KB	Output isn't correct
13	Correct	3 ms	41068 KB	Output is correct
14	Correct	9 ms	41068 KB	Output is correct
15	Incorrect	0 ms	41068 KB	Output isn't correct
16	Correct	3 ms	41068 KB	Output is correct
17	Correct	6 ms	41068 KB	Output is correct
18	Correct	6 ms	41068 KB	Output is correct
19	Correct	3 ms	41068 KB	Output is correct
20	Incorrect	3 ms	41068 KB	Output isn't correct
21	Incorrect	3 ms	41068 KB	Output isn't correct
22	Incorrect	9 ms	41068 KB	Output isn't correct
23	Correct	3 ms	41068 KB	Output is correct
24	Incorrect	3 ms	41068 KB	Output isn't correct
25	Correct	3 ms	41068 KB	Output is correct
26	Incorrect	6 ms	41068 KB	Output isn't correct
27	Correct	3 ms	41068 KB	Output is correct
28	Correct	6 ms	41068 KB	Output is correct
29	Incorrect	9 ms	41068 KB	Output isn't correct
30	Incorrect	0 ms	41068 KB	Output isn't correct
31	Incorrect	6 ms	41068 KB	Output isn't correct
32	Incorrect	0 ms	41068 KB	Output isn't correct
33	Correct	6 ms	41068 KB	Output is correct
34	Correct	3 ms	41068 KB	Output is correct
35	Correct	9 ms	41068 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	41068 KB	Output isn't correct
2	Correct	6 ms	41068 KB	Output is correct
3	Correct	3 ms	41068 KB	Output is correct
4	Incorrect	19 ms	41208 KB	Output isn't correct
5	Incorrect	496 ms	44224 KB	Output isn't correct
6	Incorrect	576 ms	44224 KB	Output isn't correct
7	Incorrect	533 ms	44224 KB	Output isn't correct
8	Correct	6 ms	41068 KB	Output is correct
9	Correct	499 ms	44224 KB	Output is correct
10	Correct	526 ms	44224 KB	Output is correct
11	Correct	203 ms	42688 KB	Output is correct
12	Correct	569 ms	44224 KB	Output is correct
13	Incorrect	563 ms	44224 KB	Output isn't correct
14	Correct	306 ms	44224 KB	Output is correct
15	Incorrect	559 ms	44224 KB	Output isn't correct
16	Correct	313 ms	44224 KB	Output is correct
17	Incorrect	579 ms	44224 KB	Output isn't correct
18	Incorrect	569 ms	44224 KB	Output isn't correct
19	Incorrect	546 ms	44224 KB	Output isn't correct

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	41068 KB	Output is correct
2	Incorrect	6 ms	41068 KB	Output isn't correct
3	Correct	3 ms	41068 KB	Output is correct
4	Incorrect	0 ms	41068 KB	Output isn't correct
5	Correct	3 ms	41068 KB	Output is correct
6	Correct	3 ms	41068 KB	Output is correct
7	Incorrect	0 ms	41068 KB	Output isn't correct
8	Incorrect	0 ms	41068 KB	Output isn't correct
9	Correct	3 ms	41068 KB	Output is correct
10	Correct	6 ms	41068 KB	Output is correct
11	Incorrect	0 ms	41068 KB	Output isn't correct
12	Incorrect	0 ms	41068 KB	Output isn't correct
13	Correct	3 ms	41068 KB	Output is correct
14	Correct	9 ms	41068 KB	Output is correct
15	Incorrect	0 ms	41068 KB	Output isn't correct
16	Correct	3 ms	41068 KB	Output is correct
17	Correct	6 ms	41068 KB	Output is correct
18	Correct	6 ms	41068 KB	Output is correct
19	Correct	3 ms	41068 KB	Output is correct
20	Incorrect	3 ms	41068 KB	Output isn't correct
21	Incorrect	3 ms	41068 KB	Output isn't correct
22	Incorrect	9 ms	41068 KB	Output isn't correct
23	Correct	3 ms	41068 KB	Output is correct
24	Incorrect	3 ms	41068 KB	Output isn't correct
25	Correct	3 ms	41068 KB	Output is correct
26	Incorrect	6 ms	41068 KB	Output isn't correct
27	Correct	3 ms	41068 KB	Output is correct
28	Correct	6 ms	41068 KB	Output is correct
29	Incorrect	9 ms	41068 KB	Output isn't correct
30	Incorrect	0 ms	41068 KB	Output isn't correct
31	Incorrect	6 ms	41068 KB	Output isn't correct
32	Incorrect	0 ms	41068 KB	Output isn't correct
33	Correct	6 ms	41068 KB	Output is correct
34	Correct	3 ms	41068 KB	Output is correct
35	Correct	9 ms	41068 KB	Output is correct
36	Incorrect	16 ms	41208 KB	Output isn't correct
37	Incorrect	16 ms	41208 KB	Output isn't correct
38	Incorrect	9 ms	41208 KB	Output isn't correct
39	Incorrect	13 ms	41208 KB	Output isn't correct
40	Incorrect	16 ms	41208 KB	Output isn't correct
41	Correct	13 ms	41208 KB	Output is correct
42	Correct	16 ms	41208 KB	Output is correct
43	Incorrect	3 ms	41068 KB	Output isn't correct
44	Incorrect	9 ms	41208 KB	Output isn't correct
45	Correct	13 ms	41208 KB	Output is correct
46	Correct	9 ms	41208 KB	Output is correct
47	Incorrect	16 ms	41208 KB	Output isn't correct
48	Incorrect	19 ms	41208 KB	Output isn't correct
49	Incorrect	16 ms	41208 KB	Output isn't correct
50	Incorrect	16 ms	41208 KB	Output isn't correct
51	Incorrect	16 ms	41208 KB	Output isn't correct
52	Incorrect	6 ms	41068 KB	Output isn't correct
53	Correct	16 ms	41208 KB	Output is correct
54	Incorrect	6 ms	41208 KB	Output isn't correct
55	Correct	13 ms	41208 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	41068 KB	Output is correct
2	Incorrect	6 ms	41068 KB	Output isn't correct
3	Correct	3 ms	41068 KB	Output is correct
4	Incorrect	0 ms	41068 KB	Output isn't correct
5	Correct	3 ms	41068 KB	Output is correct
6	Correct	3 ms	41068 KB	Output is correct
7	Incorrect	0 ms	41068 KB	Output isn't correct
8	Incorrect	0 ms	41068 KB	Output isn't correct
9	Correct	3 ms	41068 KB	Output is correct
10	Correct	6 ms	41068 KB	Output is correct
11	Incorrect	0 ms	41068 KB	Output isn't correct
12	Incorrect	0 ms	41068 KB	Output isn't correct
13	Correct	3 ms	41068 KB	Output is correct
14	Correct	9 ms	41068 KB	Output is correct
15	Incorrect	0 ms	41068 KB	Output isn't correct
16	Correct	3 ms	41068 KB	Output is correct
17	Correct	6 ms	41068 KB	Output is correct
18	Correct	6 ms	41068 KB	Output is correct
19	Correct	3 ms	41068 KB	Output is correct
20	Incorrect	3 ms	41068 KB	Output isn't correct
21	Incorrect	3 ms	41068 KB	Output isn't correct
22	Incorrect	9 ms	41068 KB	Output isn't correct
23	Correct	3 ms	41068 KB	Output is correct
24	Incorrect	3 ms	41068 KB	Output isn't correct
25	Correct	3 ms	41068 KB	Output is correct
26	Incorrect	6 ms	41068 KB	Output isn't correct
27	Correct	3 ms	41068 KB	Output is correct
28	Correct	6 ms	41068 KB	Output is correct
29	Incorrect	9 ms	41068 KB	Output isn't correct
30	Incorrect	0 ms	41068 KB	Output isn't correct
31	Incorrect	6 ms	41068 KB	Output isn't correct
32	Incorrect	0 ms	41068 KB	Output isn't correct
33	Correct	6 ms	41068 KB	Output is correct
34	Correct	3 ms	41068 KB	Output is correct
35	Correct	9 ms	41068 KB	Output is correct
36	Incorrect	3 ms	41068 KB	Output isn't correct
37	Correct	6 ms	41068 KB	Output is correct
38	Correct	3 ms	41068 KB	Output is correct
39	Incorrect	19 ms	41208 KB	Output isn't correct
40	Incorrect	496 ms	44224 KB	Output isn't correct
41	Incorrect	576 ms	44224 KB	Output isn't correct
42	Incorrect	533 ms	44224 KB	Output isn't correct
43	Correct	6 ms	41068 KB	Output is correct
44	Correct	499 ms	44224 KB	Output is correct
45	Correct	526 ms	44224 KB	Output is correct
46	Correct	203 ms	42688 KB	Output is correct
47	Correct	569 ms	44224 KB	Output is correct
48	Incorrect	563 ms	44224 KB	Output isn't correct
49	Correct	306 ms	44224 KB	Output is correct
50	Incorrect	559 ms	44224 KB	Output isn't correct
51	Correct	313 ms	44224 KB	Output is correct
52	Incorrect	579 ms	44224 KB	Output isn't correct
53	Incorrect	569 ms	44224 KB	Output isn't correct
54	Incorrect	546 ms	44224 KB	Output isn't correct
55	Incorrect	16 ms	41208 KB	Output isn't correct
56	Incorrect	16 ms	41208 KB	Output isn't correct
57	Incorrect	9 ms	41208 KB	Output isn't correct
58	Incorrect	13 ms	41208 KB	Output isn't correct
59	Incorrect	16 ms	41208 KB	Output isn't correct
60	Correct	13 ms	41208 KB	Output is correct
61	Correct	16 ms	41208 KB	Output is correct
62	Incorrect	3 ms	41068 KB	Output isn't correct
63	Incorrect	9 ms	41208 KB	Output isn't correct
64	Correct	13 ms	41208 KB	Output is correct
65	Correct	9 ms	41208 KB	Output is correct
66	Incorrect	16 ms	41208 KB	Output isn't correct
67	Incorrect	19 ms	41208 KB	Output isn't correct
68	Incorrect	16 ms	41208 KB	Output isn't correct
69	Incorrect	16 ms	41208 KB	Output isn't correct
70	Incorrect	16 ms	41208 KB	Output isn't correct
71	Incorrect	6 ms	41068 KB	Output isn't correct
72	Correct	16 ms	41208 KB	Output is correct
73	Incorrect	6 ms	41208 KB	Output isn't correct
74	Correct	13 ms	41208 KB	Output is correct
75	Incorrect	579 ms	44224 KB	Output isn't correct
76	Incorrect	373 ms	44224 KB	Output isn't correct
77	Incorrect	476 ms	44224 KB	Output isn't correct
78	Incorrect	363 ms	44224 KB	Output isn't correct
79	Correct	533 ms	44224 KB	Output is correct
80	Correct	583 ms	44224 KB	Output is correct
81	Incorrect	16 ms	41208 KB	Output isn't correct
82	Incorrect	499 ms	44224 KB	Output isn't correct
83	Correct	236 ms	44224 KB	Output is correct
84	Incorrect	503 ms	44224 KB	Output isn't correct
85	Incorrect	589 ms	44224 KB	Output isn't correct
86	Incorrect	623 ms	44224 KB	Output isn't correct
87	Incorrect	459 ms	44224 KB	Output isn't correct
88	Incorrect	456 ms	44224 KB	Output isn't correct
89	Incorrect	623 ms	44224 KB	Output isn't correct
90	Incorrect	589 ms	44224 KB	Output isn't correct
91	Incorrect	599 ms	44224 KB	Output isn't correct
92	Correct	569 ms	44224 KB	Output is correct
93	Incorrect	586 ms	44224 KB	Output isn't correct
94	Incorrect	586 ms	44224 KB	Output isn't correct
95	Incorrect	589 ms	44224 KB	Output isn't correct

답안 #20495

Compilation message

Subtask #1 0 / 10.0

Subtask #2 0 / 8.0

Subtask #3 0 / 25.0

Subtask #4 0 / 27.0

Subtask #5 0 / 30.0

Subtask #1
0 / 10.0

Subtask #2
0 / 8.0

Subtask #3
0 / 25.0

Subtask #4
0 / 27.0

Subtask #5
0 / 30.0