Submission #20847

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20847	2017-02-26T07:48:38 Z	sgc109	초음속철도 (OJUZ11_rail)	C++11	0 / 100	3000 ms	64552 KB

rail

// #include <bits/stdc++.h>
#include <unordered_set>
// #include <unordered_map>
#include <vector>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#include <map>
// #include <cmath>
#include <algorithm>
#include <utility>
#include <string>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)z
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const int MOD = 1000000007;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;

struct Range{
	int l,r;
	bool operator<(Range& rhs){
		if(l==rhs.l) return r<rhs.r;
		return l<rhs.l;
	}
};
int N,M,a,b,E;
Range ranges[200003];
ll dp[3610003];
int lz[3610003];
ll pow2(ll x, int n){
	if(!n) return 1;
	if(n%2) x*pow2(x,(n-1)/2)%MOD*pow2(x,(n-1)/2)%MOD;
	else pow2(x,n/2)*pow2(x,n/2)%MOD;
}
unordered_set<int> us;
ll query(int nl, int nr, int l, int r, int nd){
	if(lz[nd]) (dp[nd]*=pow2(2,lz[nd]))%=MOD,(nl!=nr?lz[2*nd]+=lz[nd],lz[2*nd+1]+=lz[nd]:0),lz[nd]=0;
	if(l<=nl&&nr<=r) return dp[nd];
	if(r<nl||nr<l) return 0;
	return (query(nl,(nl+nr)/2,l,r,2*nd)+query((nl+nr)/2+1,nr,l,r,2*nd+1))%MOD;
} ll query(int l, int r){return query(0,E,l,r,1);}

void update(int nl, int nr, int l, int r, int nd){
	if(lz[nd]) (dp[nd]*=pow2(2,lz[nd]))%=MOD,(nl!=nr?lz[2*nd]+=lz[nd],lz[2*nd+1]+=lz[nd]:0),lz[nd]=0;
	if(l<=nl&&nr<=r) {(dp[nd]*=2)%=MOD,(nl!=nr?lz[2*nd]++,lz[2*nd+1]++:0);return;}
	if(r<nl||nr<l) return;
	update(nl,(nl+nr)/2,l,r,2*nd),update((nl+nr)/2+1,nr,l,r,2*nd+1),dp[nd]=(dp[2*nd]+dp[2*nd+1])%MOD;
} void update(int l, int r){update(0,E,l,r,1);}

void pUpdate(int nl, int nr, int nd, int pos, ll val){
	if(lz[nd]) (dp[nd]*=pow2(2,lz[nd]))%=MOD,(nl!=nr?lz[2*nd]+=lz[nd],lz[2*nd+1]+=lz[nd]:0),lz[nd]=0;
	if(nl==nr&&nl==pos) {dp[nd]=val;return;}
	if(nr<pos||pos<nl) return;
	pUpdate(nl,(nl+nr)/2,2*nd,pos,val),pUpdate((nl+nr)/2+1,nr,2*nd+1,pos,val),dp[nd]=(dp[2*nd]+dp[2*nd+1])%MOD;
} void pUpdate(int pos, ll val){pUpdate(0,E,1,pos,val);}

int main() {
	vi sorted;
	inp2(N,M);
	us.insert(1),sorted.pb(1);
	us.insert(N),sorted.pb(N);
	FOR(i,M){
		inp2(a,b);
		ranges[i]=Range{a,b};
		if(!us.count(a)) us.insert(a),sorted.pb(a);
		if(!us.count(b)) us.insert(b),sorted.pb(b);
	}
	sort(all(sorted));
	E=sz(sorted)-1;
	FOR(i,M) {
		ranges[i].l=lower_bound(all(sorted),ranges[i].l)-sorted.begin();
		ranges[i].r=lower_bound(all(sorted),ranges[i].r)-sorted.begin();
	}
	sort(ranges,ranges+M);
	// 좌표압축 + 정렬까지 완료

	pUpdate(0,1);
	FOR(i,M){
		pUpdate(ranges[i].r,(query(ranges[i].l,ranges[i].r)+query(ranges[i].r,ranges[i].r))%MOD);
		update(ranges[i].r+1,E);
	}
	printf("%lld",query(E,E));
	return 0;
}

Compilation message

rail.cpp: In function 'll pow2(ll, int)':
rail.cpp:54:47: warning: value computed is not used [-Wunused-value]
  if(n%2) x*pow2(x,(n-1)/2)%MOD*pow2(x,(n-1)/2)%MOD;
                                               ^
rail.cpp:55:30: warning: value computed is not used [-Wunused-value]
  else pow2(x,n/2)*pow2(x,n/2)%MOD;
                              ^
rail.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
rail.cpp: In function 'int main()':
rail.cpp:81:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  inp2(N,M);
           ^
rail.cpp:85:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   inp2(a,b);
            ^

Subtask #1
0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	45900 KB	Output is correct
2	Correct	45900 KB	Output is correct
3	Incorrect	45900 KB	Output isn't correct
4	Incorrect	45900 KB	Output isn't correct
5	Correct	45900 KB	Output is correct
6	Correct	45900 KB	Output is correct
7	Incorrect	45900 KB	Output isn't correct
8	Incorrect	45900 KB	Output isn't correct
9	Correct	45900 KB	Output is correct
10	Incorrect	45900 KB	Output isn't correct
11	Correct	45900 KB	Output is correct
12	Incorrect	45900 KB	Output isn't correct
13	Correct	45900 KB	Output is correct
14	Correct	45900 KB	Output is correct
15	Incorrect	45900 KB	Output isn't correct
16	Incorrect	45900 KB	Output isn't correct
17	Correct	45900 KB	Output is correct
18	Correct	45900 KB	Output is correct

Subtask #2
0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	45900 KB	Output is correct
2	Correct	45900 KB	Output is correct
3	Incorrect	45900 KB	Output isn't correct
4	Incorrect	45900 KB	Output isn't correct
5	Correct	45900 KB	Output is correct
6	Correct	45900 KB	Output is correct
7	Incorrect	45900 KB	Output isn't correct
8	Incorrect	45900 KB	Output isn't correct
9	Correct	45900 KB	Output is correct
10	Incorrect	45900 KB	Output isn't correct
11	Correct	45900 KB	Output is correct
12	Incorrect	45900 KB	Output isn't correct
13	Correct	45900 KB	Output is correct
14	Correct	45900 KB	Output is correct
15	Incorrect	45900 KB	Output isn't correct
16	Incorrect	45900 KB	Output isn't correct
17	Correct	45900 KB	Output is correct
18	Correct	45900 KB	Output is correct
19	Correct	45900 KB	Output is correct
20	Incorrect	45900 KB	Output isn't correct
21	Correct	45900 KB	Output is correct
22	Incorrect	45900 KB	Output isn't correct
23	Incorrect	45900 KB	Output isn't correct
24	Incorrect	45900 KB	Output isn't correct
25	Incorrect	45900 KB	Output isn't correct
26	Incorrect	45900 KB	Output isn't correct
27	Correct	45900 KB	Output is correct
28	Correct	45900 KB	Output is correct
29	Incorrect	45900 KB	Output isn't correct
30	Incorrect	45900 KB	Output isn't correct
31	Incorrect	45900 KB	Output isn't correct
32	Incorrect	45900 KB	Output isn't correct
33	Correct	45900 KB	Output is correct
34	Correct	45900 KB	Output is correct
35	Correct	45900 KB	Output is correct

Subtask #3
0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	45900 KB	Output is correct
2	Incorrect	0 ms	45900 KB	Output isn't correct
3	Correct	0 ms	45900 KB	Output is correct
4	Incorrect	23 ms	46036 KB	Output isn't correct
5	Execution timed out	3000 ms	48356 KB	Execution timed out
6	Execution timed out	3000 ms	63496 KB	Execution timed out
7	Execution timed out	3000 ms	63364 KB	Execution timed out
8	Incorrect	0 ms	45900 KB	Output isn't correct
9	Execution timed out	3000 ms	62572 KB	Execution timed out
10	Execution timed out	3000 ms	63232 KB	Execution timed out
11	Execution timed out	3000 ms	47828 KB	Execution timed out
12	Execution timed out	3000 ms	63496 KB	Execution timed out
13	Execution timed out	3000 ms	63232 KB	Execution timed out
14	Correct	83 ms	45900 KB	Output is correct
15	Execution timed out	3000 ms	55260 KB	Execution timed out
16	Correct	76 ms	45900 KB	Output is correct
17	Execution timed out	3000 ms	63496 KB	Execution timed out
18	Execution timed out	3000 ms	63496 KB	Execution timed out
19	Execution timed out	3000 ms	61912 KB	Execution timed out

Subtask #4
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	45900 KB	Output is correct
2	Correct	0 ms	45900 KB	Output is correct
3	Incorrect	0 ms	45900 KB	Output isn't correct
4	Incorrect	0 ms	45900 KB	Output isn't correct
5	Correct	0 ms	45900 KB	Output is correct
6	Correct	0 ms	45900 KB	Output is correct
7	Incorrect	0 ms	45900 KB	Output isn't correct
8	Incorrect	0 ms	45900 KB	Output isn't correct
9	Correct	0 ms	45900 KB	Output is correct
10	Incorrect	0 ms	45900 KB	Output isn't correct
11	Correct	0 ms	45900 KB	Output is correct
12	Incorrect	0 ms	45900 KB	Output isn't correct
13	Correct	0 ms	45900 KB	Output is correct
14	Correct	0 ms	45900 KB	Output is correct
15	Incorrect	0 ms	45900 KB	Output isn't correct
16	Incorrect	0 ms	45900 KB	Output isn't correct
17	Correct	0 ms	45900 KB	Output is correct
18	Correct	0 ms	45900 KB	Output is correct
19	Correct	0 ms	45900 KB	Output is correct
20	Incorrect	0 ms	45900 KB	Output isn't correct
21	Correct	0 ms	45900 KB	Output is correct
22	Incorrect	0 ms	45900 KB	Output isn't correct
23	Incorrect	0 ms	45900 KB	Output isn't correct
24	Incorrect	0 ms	45900 KB	Output isn't correct
25	Incorrect	0 ms	45900 KB	Output isn't correct
26	Incorrect	0 ms	45900 KB	Output isn't correct
27	Correct	0 ms	45900 KB	Output is correct
28	Correct	0 ms	45900 KB	Output is correct
29	Incorrect	0 ms	45900 KB	Output isn't correct
30	Incorrect	0 ms	45900 KB	Output isn't correct
31	Incorrect	0 ms	45900 KB	Output isn't correct
32	Incorrect	0 ms	45900 KB	Output isn't correct
33	Correct	0 ms	45900 KB	Output is correct
34	Correct	0 ms	45900 KB	Output is correct
35	Correct	0 ms	45900 KB	Output is correct
36	Incorrect	166 ms	46420 KB	Output isn't correct
37	Incorrect	119 ms	46420 KB	Output isn't correct
38	Incorrect	46 ms	46036 KB	Output isn't correct
39	Incorrect	0 ms	45900 KB	Output isn't correct
40	Correct	136 ms	46196 KB	Output is correct
41	Correct	213 ms	46420 KB	Output is correct
42	Incorrect	169 ms	46420 KB	Output isn't correct
43	Incorrect	0 ms	45900 KB	Output isn't correct
44	Incorrect	146 ms	46196 KB	Output isn't correct
45	Correct	0 ms	45900 KB	Output is correct
46	Correct	69 ms	46196 KB	Output is correct
47	Incorrect	96 ms	46196 KB	Output isn't correct
48	Incorrect	83 ms	46196 KB	Output isn't correct
49	Incorrect	3 ms	45900 KB	Output isn't correct
50	Incorrect	3 ms	45900 KB	Output isn't correct
51	Incorrect	3 ms	45900 KB	Output isn't correct
52	Incorrect	13 ms	46036 KB	Output isn't correct
53	Correct	193 ms	46420 KB	Output is correct
54	Incorrect	33 ms	46036 KB	Output isn't correct
55	Correct	173 ms	46420 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	45900 KB	Output is correct
2	Correct	0 ms	45900 KB	Output is correct
3	Incorrect	0 ms	45900 KB	Output isn't correct
4	Incorrect	0 ms	45900 KB	Output isn't correct
5	Correct	0 ms	45900 KB	Output is correct
6	Correct	0 ms	45900 KB	Output is correct
7	Incorrect	0 ms	45900 KB	Output isn't correct
8	Incorrect	0 ms	45900 KB	Output isn't correct
9	Correct	0 ms	45900 KB	Output is correct
10	Incorrect	0 ms	45900 KB	Output isn't correct
11	Correct	0 ms	45900 KB	Output is correct
12	Incorrect	0 ms	45900 KB	Output isn't correct
13	Correct	0 ms	45900 KB	Output is correct
14	Correct	0 ms	45900 KB	Output is correct
15	Incorrect	0 ms	45900 KB	Output isn't correct
16	Incorrect	0 ms	45900 KB	Output isn't correct
17	Correct	0 ms	45900 KB	Output is correct
18	Correct	0 ms	45900 KB	Output is correct
19	Correct	0 ms	45900 KB	Output is correct
20	Incorrect	0 ms	45900 KB	Output isn't correct
21	Correct	0 ms	45900 KB	Output is correct
22	Incorrect	0 ms	45900 KB	Output isn't correct
23	Incorrect	0 ms	45900 KB	Output isn't correct
24	Incorrect	0 ms	45900 KB	Output isn't correct
25	Incorrect	0 ms	45900 KB	Output isn't correct
26	Incorrect	0 ms	45900 KB	Output isn't correct
27	Correct	0 ms	45900 KB	Output is correct
28	Correct	0 ms	45900 KB	Output is correct
29	Incorrect	0 ms	45900 KB	Output isn't correct
30	Incorrect	0 ms	45900 KB	Output isn't correct
31	Incorrect	0 ms	45900 KB	Output isn't correct
32	Incorrect	0 ms	45900 KB	Output isn't correct
33	Correct	0 ms	45900 KB	Output is correct
34	Correct	0 ms	45900 KB	Output is correct
35	Correct	0 ms	45900 KB	Output is correct
36	Correct	0 ms	45900 KB	Output is correct
37	Incorrect	0 ms	45900 KB	Output isn't correct
38	Correct	0 ms	45900 KB	Output is correct
39	Incorrect	23 ms	46036 KB	Output isn't correct
40	Execution timed out	3000 ms	48356 KB	Execution timed out
41	Execution timed out	3000 ms	63496 KB	Execution timed out
42	Execution timed out	3000 ms	63364 KB	Execution timed out
43	Incorrect	0 ms	45900 KB	Output isn't correct
44	Execution timed out	3000 ms	62572 KB	Execution timed out
45	Execution timed out	3000 ms	63232 KB	Execution timed out
46	Execution timed out	3000 ms	47828 KB	Execution timed out
47	Execution timed out	3000 ms	63496 KB	Execution timed out
48	Execution timed out	3000 ms	63232 KB	Execution timed out
49	Correct	83 ms	45900 KB	Output is correct
50	Execution timed out	3000 ms	55260 KB	Execution timed out
51	Correct	76 ms	45900 KB	Output is correct
52	Execution timed out	3000 ms	63496 KB	Execution timed out
53	Execution timed out	3000 ms	63496 KB	Execution timed out
54	Execution timed out	3000 ms	61912 KB	Execution timed out
55	Incorrect	166 ms	46420 KB	Output isn't correct
56	Incorrect	119 ms	46420 KB	Output isn't correct
57	Incorrect	46 ms	46036 KB	Output isn't correct
58	Incorrect	0 ms	45900 KB	Output isn't correct
59	Correct	136 ms	46196 KB	Output is correct
60	Correct	213 ms	46420 KB	Output is correct
61	Incorrect	169 ms	46420 KB	Output isn't correct
62	Incorrect	0 ms	45900 KB	Output isn't correct
63	Incorrect	146 ms	46196 KB	Output isn't correct
64	Correct	0 ms	45900 KB	Output is correct
65	Correct	69 ms	46196 KB	Output is correct
66	Incorrect	96 ms	46196 KB	Output isn't correct
67	Incorrect	83 ms	46196 KB	Output isn't correct
68	Incorrect	3 ms	45900 KB	Output isn't correct
69	Incorrect	3 ms	45900 KB	Output isn't correct
70	Incorrect	3 ms	45900 KB	Output isn't correct
71	Incorrect	13 ms	46036 KB	Output isn't correct
72	Correct	193 ms	46420 KB	Output is correct
73	Incorrect	33 ms	46036 KB	Output isn't correct
74	Correct	173 ms	46420 KB	Output is correct
75	Execution timed out	3000 ms	64552 KB	Execution timed out
76	Execution timed out	3000 ms	61044 KB	Execution timed out
77	Incorrect	2246 ms	46036 KB	Output isn't correct
78	Incorrect	76 ms	45900 KB	Output isn't correct
79	Execution timed out	3000 ms	49772 KB	Execution timed out
80	Execution timed out	3000 ms	64552 KB	Execution timed out
81	Incorrect	86 ms	46196 KB	Output isn't correct
82	Execution timed out	3000 ms	63100 KB	Execution timed out
83	Correct	63 ms	45900 KB	Output is correct
84	Execution timed out	3000 ms	61384 KB	Execution timed out
85	Execution timed out	3000 ms	55128 KB	Execution timed out
86	Execution timed out	3000 ms	55260 KB	Execution timed out
87	Incorrect	176 ms	45900 KB	Output isn't correct
88	Incorrect	159 ms	45900 KB	Output isn't correct
89	Execution timed out	3000 ms	64552 KB	Execution timed out
90	Execution timed out	3000 ms	64552 KB	Execution timed out
91	Execution timed out	3000 ms	64552 KB	Execution timed out
92	Execution timed out	3000 ms	64156 KB	Execution timed out
93	Execution timed out	3000 ms	55128 KB	Execution timed out
94	Execution timed out	3000 ms	64552 KB	Execution timed out
95	Execution timed out	3000 ms	64552 KB	Execution timed out

Submission #20847

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