oj.uz

Submission #20495

# Submission time Handle Problem Language Result Execution time Memory
20495 2017-02-12T05:55:10 Z 안녕하세요 투어리스트입니다 진짜에요(#49, Namnamseo) 초음속철도 (OJUZ11_rail) C++14
0 / 100
 623 ms 44224 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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