답안 #20846 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20846	2017-02-26T07:22:48 Z	sgc109	초음속철도 (OJUZ11_rail)	C++11	18 / 100	1343 ms	78836 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];
ll lz[3610003];
ll pow(ll x, ll n){
	if(n==0) return 1;
	if(n%2) (x*pow(x,(n-1)/2))%MOD*pow(x,(n-1)/2)%MOD;
	else pow(x,n/2)*pow(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]*=pow(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]*=pow(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]*=pow(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 pow(ll, ll)':
rail.cpp:54:47: warning: value computed is not used [-Wunused-value]
  if(n%2) (x*pow(x,(n-1)/2))%MOD*pow(x,(n-1)/2)%MOD;
                                               ^
rail.cpp:55:28: warning: value computed is not used [-Wunused-value]
  else pow(x,n/2)*pow(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
10.0 / 10.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	60184 KB	Output is correct
2	Correct	0 ms	60184 KB	Output is correct
3	Correct	0 ms	60184 KB	Output is correct
4	Incorrect	3 ms	60320 KB	Output isn't correct
5	Incorrect	263 ms	62640 KB	Output isn't correct
6	Incorrect	633 ms	77780 KB	Output isn't correct
7	Incorrect	559 ms	77648 KB	Output isn't correct
8	Correct	0 ms	60184 KB	Output is correct
9	Incorrect	569 ms	76856 KB	Output isn't correct
10	Incorrect	629 ms	77516 KB	Output isn't correct
11	Incorrect	169 ms	62112 KB	Output isn't correct
12	Incorrect	659 ms	77780 KB	Output isn't correct
13	Incorrect	666 ms	77516 KB	Output isn't correct
14	Incorrect	86 ms	60184 KB	Output isn't correct
15	Incorrect	576 ms	69544 KB	Output isn't correct
16	Incorrect	86 ms	60184 KB	Output isn't correct
17	Incorrect	676 ms	77780 KB	Output isn't correct
18	Incorrect	703 ms	77780 KB	Output isn't correct
19	Incorrect	659 ms	76196 KB	Output isn't correct

Subtask #4
0 / 27.0

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

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	60184 KB	Output is correct
2	Correct	0 ms	60184 KB	Output is correct
3	Correct	0 ms	60184 KB	Output is correct
4	Correct	0 ms	60184 KB	Output is correct
5	Correct	0 ms	60184 KB	Output is correct
6	Correct	0 ms	60184 KB	Output is correct
7	Correct	0 ms	60184 KB	Output is correct
8	Correct	0 ms	60184 KB	Output is correct
9	Correct	0 ms	60184 KB	Output is correct
10	Correct	0 ms	60184 KB	Output is correct
11	Correct	0 ms	60184 KB	Output is correct
12	Correct	0 ms	60184 KB	Output is correct
13	Correct	0 ms	60184 KB	Output is correct
14	Correct	0 ms	60184 KB	Output is correct
15	Correct	0 ms	60184 KB	Output is correct
16	Correct	0 ms	60184 KB	Output is correct
17	Correct	0 ms	60184 KB	Output is correct
18	Correct	0 ms	60184 KB	Output is correct
19	Correct	0 ms	60184 KB	Output is correct
20	Correct	0 ms	60184 KB	Output is correct
21	Correct	0 ms	60184 KB	Output is correct
22	Correct	0 ms	60184 KB	Output is correct
23	Correct	0 ms	60184 KB	Output is correct
24	Correct	0 ms	60184 KB	Output is correct
25	Correct	0 ms	60184 KB	Output is correct
26	Correct	0 ms	60184 KB	Output is correct
27	Correct	0 ms	60184 KB	Output is correct
28	Correct	0 ms	60184 KB	Output is correct
29	Correct	0 ms	60184 KB	Output is correct
30	Correct	0 ms	60184 KB	Output is correct
31	Correct	0 ms	60184 KB	Output is correct
32	Correct	0 ms	60184 KB	Output is correct
33	Correct	0 ms	60184 KB	Output is correct
34	Correct	0 ms	60184 KB	Output is correct
35	Correct	0 ms	60184 KB	Output is correct
36	Correct	0 ms	60184 KB	Output is correct
37	Correct	0 ms	60184 KB	Output is correct
38	Correct	0 ms	60184 KB	Output is correct
39	Incorrect	3 ms	60320 KB	Output isn't correct
40	Incorrect	263 ms	62640 KB	Output isn't correct
41	Incorrect	633 ms	77780 KB	Output isn't correct
42	Incorrect	559 ms	77648 KB	Output isn't correct
43	Correct	0 ms	60184 KB	Output is correct
44	Incorrect	569 ms	76856 KB	Output isn't correct
45	Incorrect	629 ms	77516 KB	Output isn't correct
46	Incorrect	169 ms	62112 KB	Output isn't correct
47	Incorrect	659 ms	77780 KB	Output isn't correct
48	Incorrect	666 ms	77516 KB	Output isn't correct
49	Incorrect	86 ms	60184 KB	Output isn't correct
50	Incorrect	576 ms	69544 KB	Output isn't correct
51	Incorrect	86 ms	60184 KB	Output isn't correct
52	Incorrect	676 ms	77780 KB	Output isn't correct
53	Incorrect	703 ms	77780 KB	Output isn't correct
54	Incorrect	659 ms	76196 KB	Output isn't correct
55	Incorrect	19 ms	60704 KB	Output isn't correct
56	Incorrect	16 ms	60704 KB	Output isn't correct
57	Incorrect	9 ms	60320 KB	Output isn't correct
58	Incorrect	0 ms	60184 KB	Output isn't correct
59	Incorrect	6 ms	60480 KB	Output isn't correct
60	Incorrect	19 ms	60704 KB	Output isn't correct
61	Incorrect	16 ms	60704 KB	Output isn't correct
62	Correct	0 ms	60184 KB	Output is correct
63	Incorrect	13 ms	60480 KB	Output isn't correct
64	Correct	0 ms	60184 KB	Output is correct
65	Incorrect	6 ms	60480 KB	Output isn't correct
66	Incorrect	13 ms	60480 KB	Output isn't correct
67	Incorrect	9 ms	60480 KB	Output isn't correct
68	Incorrect	3 ms	60184 KB	Output isn't correct
69	Incorrect	3 ms	60184 KB	Output isn't correct
70	Incorrect	3 ms	60184 KB	Output isn't correct
71	Incorrect	3 ms	60320 KB	Output isn't correct
72	Incorrect	19 ms	60704 KB	Output isn't correct
73	Incorrect	6 ms	60320 KB	Output isn't correct
74	Incorrect	19 ms	60704 KB	Output isn't correct
75	Incorrect	1336 ms	78836 KB	Output isn't correct
76	Incorrect	783 ms	75328 KB	Output isn't correct
77	Incorrect	409 ms	60320 KB	Output isn't correct
78	Incorrect	73 ms	60184 KB	Output isn't correct
79	Incorrect	756 ms	64056 KB	Output isn't correct
80	Incorrect	1243 ms	78836 KB	Output isn't correct
81	Incorrect	13 ms	60480 KB	Output isn't correct
82	Incorrect	1116 ms	77384 KB	Output isn't correct
83	Correct	66 ms	60184 KB	Output is correct
84	Incorrect	916 ms	75668 KB	Output isn't correct
85	Incorrect	856 ms	69412 KB	Output isn't correct
86	Incorrect	879 ms	69544 KB	Output isn't correct
87	Incorrect	166 ms	60184 KB	Output isn't correct
88	Incorrect	159 ms	60184 KB	Output isn't correct
89	Incorrect	1309 ms	78836 KB	Output isn't correct
90	Incorrect	1343 ms	78836 KB	Output isn't correct
91	Incorrect	1279 ms	78836 KB	Output isn't correct
92	Incorrect	1139 ms	78440 KB	Output isn't correct
93	Incorrect	809 ms	69412 KB	Output isn't correct
94	Incorrect	1266 ms	78836 KB	Output isn't correct
95	Incorrect	1319 ms	78836 KB	Output isn't correct

답안 #20846

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 8.0 / 8.0

Subtask #3 0 / 25.0

Subtask #4 0 / 27.0

Subtask #5 0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
8.0 / 8.0

Subtask #3
0 / 25.0

Subtask #4
0 / 27.0

Subtask #5
0 / 30.0