답안 #20843 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20843	2017-02-26T06:53:52 Z	sgc109	초음속철도 (OJUZ11_rail)	C++11	0 / 100	883 ms	78652 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 double EPSILON = 1e-9;
const double PI = acos(-1);
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];
ll lz[3610003];
unordered_set<int> us;
ll query(int nl, int nr, int l, int r, int nd){
	if(lz[nd]) (dp[nd]*=2)%=MOD,(nl!=nr?lz[2*nd]=1,lz[2*nd+1]=1: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]*=2)%=MOD,(nl!=nr?lz[2*nd]=1,lz[2*nd+1]=1:0),lz[nd]=0;
	if(l<=nl&&nr<=r) {(dp[nd]*=2)%=MOD,(nl!=nr?lz[2*nd]=lz[2*nd+1]=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, int val){
	if(lz[nd]) (dp[nd]*=2)%=MOD,(nl!=nr?lz[2*nd]=1,lz[2*nd+1]=1: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, int 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));
		update(ranges[i].r+1,E);
	}
	printf("%lld",query(E,E));
	return 0;
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:78:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  inp2(N,M);
           ^
rail.cpp:82: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

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	60000 KB	Output is correct
2	Correct	0 ms	60000 KB	Output is correct
3	Correct	0 ms	60000 KB	Output is correct
4	Incorrect	3 ms	60136 KB	Output isn't correct
5	Incorrect	276 ms	62456 KB	Output isn't correct
6	Incorrect	683 ms	77596 KB	Output isn't correct
7	Incorrect	559 ms	77464 KB	Output isn't correct
8	Incorrect	0 ms	60000 KB	Output isn't correct
9	Incorrect	563 ms	76672 KB	Output isn't correct
10	Incorrect	616 ms	77332 KB	Output isn't correct
11	Incorrect	186 ms	61928 KB	Output isn't correct
12	Incorrect	643 ms	77596 KB	Output isn't correct
13	Incorrect	636 ms	77332 KB	Output isn't correct
14	Correct	89 ms	60000 KB	Output is correct
15	Correct	533 ms	69360 KB	Output is correct
16	Correct	76 ms	60000 KB	Output is correct
17	Incorrect	646 ms	77596 KB	Output isn't correct
18	Incorrect	636 ms	77596 KB	Output isn't correct
19	Incorrect	613 ms	76012 KB	Output isn't correct

Subtask #4
0 / 27.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	60000 KB	Output is correct
2	Correct	0 ms	60000 KB	Output is correct
3	Incorrect	0 ms	60000 KB	Output isn't correct
4	Incorrect	0 ms	60000 KB	Output isn't correct
5	Correct	0 ms	60000 KB	Output is correct
6	Correct	0 ms	60000 KB	Output is correct
7	Incorrect	0 ms	60000 KB	Output isn't correct
8	Incorrect	0 ms	60000 KB	Output isn't correct
9	Correct	0 ms	60000 KB	Output is correct
10	Incorrect	0 ms	60000 KB	Output isn't correct
11	Correct	0 ms	60000 KB	Output is correct
12	Incorrect	0 ms	60000 KB	Output isn't correct
13	Correct	0 ms	60000 KB	Output is correct
14	Correct	0 ms	60000 KB	Output is correct
15	Incorrect	0 ms	60000 KB	Output isn't correct
16	Incorrect	0 ms	60000 KB	Output isn't correct
17	Correct	0 ms	60000 KB	Output is correct
18	Correct	0 ms	60000 KB	Output is correct
19	Correct	0 ms	60000 KB	Output is correct
20	Incorrect	0 ms	60000 KB	Output isn't correct
21	Correct	0 ms	60000 KB	Output is correct
22	Incorrect	0 ms	60000 KB	Output isn't correct
23	Incorrect	0 ms	60000 KB	Output isn't correct
24	Incorrect	0 ms	60000 KB	Output isn't correct
25	Incorrect	0 ms	60000 KB	Output isn't correct
26	Incorrect	0 ms	60000 KB	Output isn't correct
27	Correct	0 ms	60000 KB	Output is correct
28	Correct	0 ms	60000 KB	Output is correct
29	Incorrect	0 ms	60000 KB	Output isn't correct
30	Incorrect	0 ms	60000 KB	Output isn't correct
31	Incorrect	0 ms	60000 KB	Output isn't correct
32	Incorrect	0 ms	60000 KB	Output isn't correct
33	Correct	0 ms	60000 KB	Output is correct
34	Correct	0 ms	60000 KB	Output is correct
35	Correct	0 ms	60000 KB	Output is correct
36	Correct	0 ms	60000 KB	Output is correct
37	Correct	0 ms	60000 KB	Output is correct
38	Correct	0 ms	60000 KB	Output is correct
39	Incorrect	3 ms	60136 KB	Output isn't correct
40	Incorrect	276 ms	62456 KB	Output isn't correct
41	Incorrect	683 ms	77596 KB	Output isn't correct
42	Incorrect	559 ms	77464 KB	Output isn't correct
43	Incorrect	0 ms	60000 KB	Output isn't correct
44	Incorrect	563 ms	76672 KB	Output isn't correct
45	Incorrect	616 ms	77332 KB	Output isn't correct
46	Incorrect	186 ms	61928 KB	Output isn't correct
47	Incorrect	643 ms	77596 KB	Output isn't correct
48	Incorrect	636 ms	77332 KB	Output isn't correct
49	Correct	89 ms	60000 KB	Output is correct
50	Correct	533 ms	69360 KB	Output is correct
51	Correct	76 ms	60000 KB	Output is correct
52	Incorrect	646 ms	77596 KB	Output isn't correct
53	Incorrect	636 ms	77596 KB	Output isn't correct
54	Incorrect	613 ms	76012 KB	Output isn't correct
55	Incorrect	13 ms	60520 KB	Output isn't correct
56	Incorrect	9 ms	60520 KB	Output isn't correct
57	Incorrect	6 ms	60136 KB	Output isn't correct
58	Incorrect	0 ms	60000 KB	Output isn't correct
59	Correct	6 ms	60296 KB	Output is correct
60	Correct	6 ms	60520 KB	Output is correct
61	Incorrect	13 ms	60520 KB	Output isn't correct
62	Incorrect	0 ms	60000 KB	Output isn't correct
63	Incorrect	9 ms	60296 KB	Output isn't correct
64	Correct	0 ms	60000 KB	Output is correct
65	Correct	6 ms	60296 KB	Output is correct
66	Incorrect	9 ms	60296 KB	Output isn't correct
67	Incorrect	6 ms	60296 KB	Output isn't correct
68	Incorrect	3 ms	60000 KB	Output isn't correct
69	Incorrect	3 ms	60000 KB	Output isn't correct
70	Incorrect	3 ms	60000 KB	Output isn't correct
71	Incorrect	0 ms	60136 KB	Output isn't correct
72	Correct	9 ms	60520 KB	Output is correct
73	Incorrect	3 ms	60136 KB	Output isn't correct
74	Correct	9 ms	60520 KB	Output is correct
75	Incorrect	883 ms	78652 KB	Output isn't correct
76	Incorrect	533 ms	75144 KB	Output isn't correct
77	Incorrect	303 ms	60136 KB	Output isn't correct
78	Incorrect	76 ms	60000 KB	Output isn't correct
79	Correct	489 ms	63872 KB	Output is correct
80	Incorrect	836 ms	78652 KB	Output isn't correct
81	Incorrect	9 ms	60296 KB	Output isn't correct
82	Incorrect	773 ms	77200 KB	Output isn't correct
83	Correct	63 ms	60000 KB	Output is correct
84	Incorrect	663 ms	75484 KB	Output isn't correct
85	Incorrect	633 ms	69228 KB	Output isn't correct
86	Incorrect	653 ms	69360 KB	Output isn't correct
87	Incorrect	156 ms	60000 KB	Output isn't correct
88	Incorrect	143 ms	60000 KB	Output isn't correct
89	Incorrect	849 ms	78652 KB	Output isn't correct
90	Incorrect	859 ms	78652 KB	Output isn't correct
91	Incorrect	883 ms	78652 KB	Output isn't correct
92	Correct	769 ms	78256 KB	Output is correct
93	Incorrect	656 ms	69228 KB	Output isn't correct
94	Incorrect	846 ms	78652 KB	Output isn't correct
95	Incorrect	873 ms	78652 KB	Output isn't correct

답안 #20843

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