oj.uz

Submission #20420

# Submission time Handle Problem Language Result Execution time Memory
20420 2017-02-11T10:45:04 Z admin 초음속철도 (OJUZ11_rail) C++14
0 / 100
 1226 ms 25172 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
 
#define debug(format, ...) printf(format, __VA_ARGS__);
 
const int M_ = 200500;
const int MAX_TREE_SIZE = 1<<20;
 
const int MOD = (ll)1e9 + 7;
 
class modint {
	int v;
public:
	modint (): v(0) { }
	modint (ll v): v((v + MOD) % MOD) { }
 
	bool operator== (modint x) { return v == x.v; }
	bool operator!= (modint x) { return v != x.v; }
 
	modint operator+ (modint x) { return v + x.v; }
	modint operator- (modint x) { return v - x.v; }
	modint operator* (modint x) { return (ll)v * x.v; }
 
	modint& operator+= (const modint x) { return *this = (*this + x); }
	modint& operator-= (const modint x) { return *this = (*this - x); }
	modint& operator*= (const modint x) { return *this = (*this * x); }
 
	int operator* () { return v; }
};
 
int F, N, M;
vector< pair<int, int> > intervals;
vector< int* > renum;
 
// 서브태스크:
//	1. n, m <= 20
//	2. n <= 20 (합쳐서 10점)
//	3. n <= 1000, m <= 1000
//	4. 포함 관계
//	5. n <= 500000, m <= 500000
 
namespace segtree {
	struct node {
		modint sum, mul, add;
		node(modint sum = 0, modint mul = 1, modint add = 0): sum(sum), mul(mul), add(add) { }
	};
 
	vector<node> tree(MAX_TREE_SIZE + 1);
 
	void spread (int idx, int nl, int nr) {
		node& nd = tree[idx];
		node& c1 = (nl == nr) ? tree[0] : tree[idx * 2];
		node& c2 = (nl == nr) ? tree[0] : tree[idx * 2 + 1];
 
		if(nd.mul != 1) {
			nd.sum *= nd.mul;
			for(auto &child : {&c1, &c2}) {
				child->mul *= nd.mul;
				child->add *= nd.mul;
			}
			nd.mul = 1;
		}
 
		if(nd.add != 0) {
			nd.sum += nd.add * (nr - nl + 1);
			for(auto &child : {&c1, &c2}) {
				child->add += nd.add;
			}
			nd.add = 0;
		}
	}
 
	modint update (int idx, int nl, int nr, int l, int r, char type, modint v) {
		if(l > r) return 0;
		node &nd = tree[idx];
		spread(idx, nl, nr);
		if(l <= nl && nr <= r) {
			(type == '*' ? nd.mul : nd.add) = v;
			spread(idx, nl, nr);
			return nd.sum;
		}
		int nm = (nl + nr) >> 1;
		nd.sum = 0;
		if(l <= nm) nd.sum += update(idx*2,	 nl, nm,	 l, min(nm, r),	 type, v);
		if(r >	nm) nd.sum += update(idx*2+1, nm+1, nr, max(nm+1, l), r, type, v);
		return nd.sum;
	}
 
	void multiply(int l, int r, modint v) {
		update(1, 0, N, l, r, '*', v);
	}
 
	void add (int l, int r, modint v) {
		update(1, 0, N, l, r, '+', v);
	}
 
	modint get (int idx, int nl, int nr, int x) {
		spread(idx, nl, nr);
		if(nl == nr) return tree[idx].sum;
		int nm = (nl + nr) >> 1;
		return (x <= nm) ?
								get(idx*2,	 nl, nm,	 x) :
								get(idx*2+1, nm+1, nr, x);
	}
 
	modint get(int x) {
		return get(1, 0, N, x);
	}
};
 
modint ans;
 
int main() {
	assert(scanf("%d%d", &N, &M) == 2);
  while(M > 200000);
	intervals.resize(M);
	renum.reserve(2*M);
	for(auto &interval : intervals) {
		assert(scanf("%d%d", &interval.first, &interval.second) == 2);
		assert(1 <= interval.first && interval.first < interval.second && interval.second <= N);
		renum.push_back(&interval.first);
		renum.push_back(&interval.second);
	}
	F = 1;
	renum.push_back(&F);
	renum.push_back(&N);
 
 
	sort(renum.begin(), renum.end(), [&](const int *a, const int *b){
		return *a < *b;
	});
 
	for(int i = 0, k = 0; i < renum.size(); ) {
		int j = i, v = *renum[i];
		k += 1;
		for(; j < renum.size() && *renum[j] == v; j++) *renum[j] = k;
		i = j;
	}
 
	for(auto &interval : intervals) {
		interval.second -= 1;
	}
	N -= 1;
 
	segtree::add(0, 0, 1);
	for(auto &interval : intervals) {
		int l, r; tie(l, r) = interval;
		modint v = segtree::get(l-1);
		segtree::multiply(0, l-1, 2);
		segtree::add(l, r, v);
		segtree::multiply(r+1, N, 2);
	}
 
	ans = segtree::get(N);
	printf("%d\n", *ans);
	return 0;
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:161:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, k = 0; i < renum.size(); ) {
                          ^
rail.cpp:164:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j < renum.size() && *renum[j] == v; j++) *renum[j] = k;
           ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14228 KB Output is correct
2 Correct 3 ms 14228 KB Output is correct
3 Correct 0 ms 14228 KB Output is correct
4 Incorrect 13 ms 14580 KB Output isn't correct
5 Incorrect 416 ms 25172 KB Output isn't correct
6 Correct 756 ms 25172 KB Output is correct
7 Correct 756 ms 25172 KB Output is correct
8 Correct 0 ms 14228 KB Output is correct
9 Correct 679 ms 24348 KB Output is correct
10 Correct 703 ms 24892 KB Output is correct
11 Correct 326 ms 21004 KB Output is correct
12 Correct 743 ms 25172 KB Output is correct
13 Correct 726 ms 24976 KB Output is correct
14 Correct 103 ms 25172 KB Output is correct
15 Incorrect 683 ms 25172 KB Output isn't correct
16 Correct 96 ms 25172 KB Output is correct
17 Correct 773 ms 25172 KB Output is correct
18 Correct 783 ms 25172 KB Output is correct
19 Correct 766 ms 25172 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14228 KB Output is correct
2 Incorrect 3 ms 14228 KB Output isn't correct
3 Incorrect 3 ms 14228 KB Output isn't correct
4 Incorrect 0 ms 14228 KB Output isn't correct
5 Correct 0 ms 14228 KB Output is correct
6 Correct 0 ms 14228 KB Output is correct
7 Incorrect 0 ms 14228 KB Output isn't correct
8 Incorrect 3 ms 14228 KB Output isn't correct
9 Correct 0 ms 14228 KB Output is correct
10 Incorrect 3 ms 14228 KB Output isn't correct
11 Incorrect 0 ms 14228 KB Output isn't correct
12 Incorrect 0 ms 14228 KB Output isn't correct
13 Correct 0 ms 14228 KB Output is correct
14 Correct 0 ms 14228 KB Output is correct
15 Incorrect 3 ms 14228 KB Output isn't correct
16 Incorrect 0 ms 14228 KB Output isn't correct
17 Correct 3 ms 14228 KB Output is correct
18 Correct 0 ms 14228 KB Output is correct
19 Incorrect 0 ms 14228 KB Output isn't correct
20 Incorrect 0 ms 14228 KB Output isn't correct
21 Incorrect 3 ms 14228 KB Output isn't correct
22 Incorrect 6 ms 14228 KB Output isn't correct
23 Incorrect 0 ms 14228 KB Output isn't correct
24 Incorrect 0 ms 14228 KB Output isn't correct
25 Incorrect 0 ms 14228 KB Output isn't correct
26 Incorrect 0 ms 14228 KB Output isn't correct
27 Correct 0 ms 14228 KB Output is correct
28 Correct 3 ms 14228 KB Output is correct
29 Incorrect 0 ms 14228 KB Output isn't correct
30 Incorrect 3 ms 14228 KB Output isn't correct
31 Incorrect 3 ms 14228 KB Output isn't correct
32 Incorrect 6 ms 14228 KB Output isn't correct
33 Correct 3 ms 14228 KB Output is correct
34 Correct 3 ms 14228 KB Output is correct
35 Correct 3 ms 14228 KB Output is correct
36 Incorrect 13 ms 14580 KB Output isn't correct
37 Incorrect 9 ms 14400 KB Output isn't correct
38 Incorrect 13 ms 14400 KB Output isn't correct
39 Incorrect 3 ms 14580 KB Output isn't correct
40 Incorrect 13 ms 14580 KB Output isn't correct
41 Correct 13 ms 14580 KB Output is correct
42 Incorrect 13 ms 14580 KB Output isn't correct
43 Incorrect 0 ms 14228 KB Output isn't correct
44 Incorrect 13 ms 14576 KB Output isn't correct
45 Correct 3 ms 14580 KB Output is correct
46 Incorrect 9 ms 14580 KB Output isn't correct
47 Incorrect 13 ms 14580 KB Output isn't correct
48 Incorrect 13 ms 14580 KB Output isn't correct
49 Incorrect 6 ms 14580 KB Output isn't correct
50 Incorrect 9 ms 14580 KB Output isn't correct
51 Incorrect 6 ms 14580 KB Output isn't correct
52 Incorrect 3 ms 14360 KB Output isn't correct
53 Correct 9 ms 14580 KB Output is correct
54 Incorrect 9 ms 14376 KB Output isn't correct
55 Correct 13 ms 14580 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14228 KB Output is correct
2 Incorrect 3 ms 14228 KB Output isn't correct
3 Incorrect 3 ms 14228 KB Output isn't correct
4 Incorrect 0 ms 14228 KB Output isn't correct
5 Correct 0 ms 14228 KB Output is correct
6 Correct 0 ms 14228 KB Output is correct
7 Incorrect 0 ms 14228 KB Output isn't correct
8 Incorrect 3 ms 14228 KB Output isn't correct
9 Correct 0 ms 14228 KB Output is correct
10 Incorrect 3 ms 14228 KB Output isn't correct
11 Incorrect 0 ms 14228 KB Output isn't correct
12 Incorrect 0 ms 14228 KB Output isn't correct
13 Correct 0 ms 14228 KB Output is correct
14 Correct 0 ms 14228 KB Output is correct
15 Incorrect 3 ms 14228 KB Output isn't correct
16 Incorrect 0 ms 14228 KB Output isn't correct
17 Correct 3 ms 14228 KB Output is correct
18 Correct 0 ms 14228 KB Output is correct
19 Incorrect 0 ms 14228 KB Output isn't correct
20 Incorrect 0 ms 14228 KB Output isn't correct
21 Incorrect 3 ms 14228 KB Output isn't correct
22 Incorrect 6 ms 14228 KB Output isn't correct
23 Incorrect 0 ms 14228 KB Output isn't correct
24 Incorrect 0 ms 14228 KB Output isn't correct
25 Incorrect 0 ms 14228 KB Output isn't correct
26 Incorrect 0 ms 14228 KB Output isn't correct
27 Correct 0 ms 14228 KB Output is correct
28 Correct 3 ms 14228 KB Output is correct
29 Incorrect 0 ms 14228 KB Output isn't correct
30 Incorrect 3 ms 14228 KB Output isn't correct
31 Incorrect 3 ms 14228 KB Output isn't correct
32 Incorrect 6 ms 14228 KB Output isn't correct
33 Correct 3 ms 14228 KB Output is correct
34 Correct 3 ms 14228 KB Output is correct
35 Correct 3 ms 14228 KB Output is correct
36 Correct 3 ms 14228 KB Output is correct
37 Correct 3 ms 14228 KB Output is correct
38 Correct 0 ms 14228 KB Output is correct
39 Incorrect 13 ms 14580 KB Output isn't correct
40 Incorrect 416 ms 25172 KB Output isn't correct
41 Correct 756 ms 25172 KB Output is correct
42 Correct 756 ms 25172 KB Output is correct
43 Correct 0 ms 14228 KB Output is correct
44 Correct 679 ms 24348 KB Output is correct
45 Correct 703 ms 24892 KB Output is correct
46 Correct 326 ms 21004 KB Output is correct
47 Correct 743 ms 25172 KB Output is correct
48 Correct 726 ms 24976 KB Output is correct
49 Correct 103 ms 25172 KB Output is correct
50 Incorrect 683 ms 25172 KB Output isn't correct
51 Correct 96 ms 25172 KB Output is correct
52 Correct 773 ms 25172 KB Output is correct
53 Correct 783 ms 25172 KB Output is correct
54 Correct 766 ms 25172 KB Output is correct
55 Incorrect 13 ms 14580 KB Output isn't correct
56 Incorrect 9 ms 14400 KB Output isn't correct
57 Incorrect 13 ms 14400 KB Output isn't correct
58 Incorrect 3 ms 14580 KB Output isn't correct
59 Incorrect 13 ms 14580 KB Output isn't correct
60 Correct 13 ms 14580 KB Output is correct
61 Incorrect 13 ms 14580 KB Output isn't correct
62 Incorrect 0 ms 14228 KB Output isn't correct
63 Incorrect 13 ms 14576 KB Output isn't correct
64 Correct 3 ms 14580 KB Output is correct
65 Incorrect 9 ms 14580 KB Output isn't correct
66 Incorrect 13 ms 14580 KB Output isn't correct
67 Incorrect 13 ms 14580 KB Output isn't correct
68 Incorrect 6 ms 14580 KB Output isn't correct
69 Incorrect 9 ms 14580 KB Output isn't correct
70 Incorrect 6 ms 14580 KB Output isn't correct
71 Incorrect 3 ms 14360 KB Output isn't correct
72 Correct 9 ms 14580 KB Output is correct
73 Incorrect 9 ms 14376 KB Output isn't correct
74 Correct 13 ms 14580 KB Output is correct
75 Incorrect 1189 ms 25172 KB Output isn't correct
76 Incorrect 733 ms 21408 KB Output isn't correct
77 Incorrect 543 ms 24672 KB Output isn't correct
78 Incorrect 93 ms 25172 KB Output isn't correct
79 Correct 666 ms 25120 KB Output is correct
80 Correct 1196 ms 25172 KB Output is correct
81 Incorrect 16 ms 14580 KB Output isn't correct
82 Incorrect 1143 ms 24808 KB Output isn't correct
83 Correct 79 ms 25172 KB Output is correct
84 Incorrect 936 ms 25172 KB Output isn't correct
85 Incorrect 883 ms 25172 KB Output isn't correct
86 Incorrect 1043 ms 25172 KB Output isn't correct
87 Incorrect 239 ms 25172 KB Output isn't correct
88 Incorrect 189 ms 25172 KB Output isn't correct
89 Incorrect 1086 ms 25172 KB Output isn't correct
90 Incorrect 1109 ms 25172 KB Output isn't correct
91 Incorrect 1226 ms 25172 KB Output isn't correct
92 Correct 949 ms 24968 KB Output is correct
93 Incorrect 1073 ms 25172 KB Output isn't correct
94 Incorrect 1116 ms 25172 KB Output isn't correct
95 Incorrect 1179 ms 25172 KB Output isn't correct