답안 #20494 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20494	2017-02-12T05:48:58 Z	admin	초음속철도 (OJUZ11_rail)	C++14	0 / 100	179 ms	28580 KB

rail

#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 N_ = 500500;
const int M_ = 500500;

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 N, M;
vector< pair<int, int> > intervals;
int F;
vector< int* > renum;


int main() {
	assert(scanf("%d%d", &N, &M) == 2);
	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(intervals.begin(), intervals.end());
  int mxr = 1;
  for(auto &interval : intervals) {
      if(mxr < interval.first) {
        printf("0\n");
        return 0;
      }
      mxr = max(mxr, interval.second);
  }

	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;

	sort(intervals.begin(), intervals.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
		return make_pair(a.first, -a.second) < make_pair(b.first, -b.second);
	});

	// 0. 전처리
	vector<modint> pow2(M+1);
	pow2[0] = 1;
	for(int i = 1; i <= M; i++) {
		pow2[i] = pow2[i-1] * 2;
	}

	// 1. 중복 제거
	vector< pair< pair<int, int>, int> > unique_intervals;
	for(int i = 0; i < intervals.size(); ) {
		int j = i;
		while(j < intervals.size() && intervals[i] == intervals[j])
			j += 1;
		unique_intervals.push_back(make_pair(intervals[i], j - i - (i == 0)));
		i = j;
	}

	// 2.
	stack<int> stk;
	vector< vector<int> > childs(unique_intervals.size());
	vector<int> parent(unique_intervals.size(), -1);
	vector<int> roots;
	modint ans = 1;

	for(int i = 0; i < unique_intervals.size(); i++) {
		pair<int, int> interval; int cnt;
		tie(interval, cnt) = unique_intervals[i];
		while(!stk.empty()) {
			int tp = stk.top();
			if(unique_intervals[tp].first.second < interval.first) {
				stk.pop();
			}else {
				childs[tp].push_back(i);
				parent[i] = tp;
				break;
			}
		}
		if(stk.empty()) {
			roots.push_back(i);
		}
		stk.push(i);
	}

	queue<int> que;
	vector<int> deg(unique_intervals.size());
	vector<modint> ways(unique_intervals.size());
	vector<int> subtree_size(unique_intervals.size());

	for(int i = 0; i < unique_intervals.size(); i++) {
		deg[i] = childs[i].size();
		if(deg[i] == 0) {
			que.push(i);
		}
	}

	while(!que.empty()) {
		int u = que.front(); que.pop();
		pair<int, int> interval; int cnt;
		tie(interval, cnt) = unique_intervals[u];

		subtree_size[u] += cnt;

		int p = parent[u];
		if(p >= 0) {
			if(--deg[p] == 0) que.push(p);
			subtree_size[p] += subtree_size[u];
		}

		pair<int, int> merged(-1, -1);
		for(auto ch : childs[u]) {
			if(merged.first == -1) merged = unique_intervals[ch].first;
			else if(merged.second + 1 == unique_intervals[ch].first.first)
				merged = make_pair(merged.first, unique_intervals[ch].first.second);
			else {
				merged = make_pair(-2, -2);
				break;
			}
		}

		ways[u] = pow2[subtree_size[u] - cnt] * (pow2[cnt] - 1);
		if(merged == interval) {
			modint cur = 1;
			for(int child : childs[u]) cur *= ways[child];
			ways[u] += cur;
		}
	}

	assert(roots.size() == 1);
	for(auto i : roots) {
		ans *= ways[i];
	}
	printf("%d\n", *ans);
	return 0;
}

Compilation message

rail.cpp: In function 'int main()':
rail.cpp:93:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0, k = 0; i < renum.size(); ) {
                          ^
rail.cpp:96:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j < renum.size() && *renum[j] == v; j++) *renum[j] = k;
           ^
rail.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < intervals.size(); ) {
                   ^
rail.cpp:120:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j < intervals.size() && intervals[i] == intervals[j])
           ^
rail.cpp:133:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < unique_intervals.size(); i++) {
                   ^
rail.cpp:157:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < unique_intervals.size(); i++) {
                   ^

Subtask #1
0 / 10.0

#	결과	메모리	Grader output
1	Incorrect	1944 KB	Output isn't correct
2	Runtime error	1948 KB	Execution killed because of forbidden syscall gettid (186)
3	Incorrect	1944 KB	Output isn't correct
4	Incorrect	1944 KB	Output isn't correct
5	Correct	1944 KB	Output is correct
6	Incorrect	1944 KB	Output isn't correct
7	Incorrect	1944 KB	Output isn't correct
8	Incorrect	1944 KB	Output isn't correct
9	Correct	1944 KB	Output is correct
10	Incorrect	1944 KB	Output isn't correct
11	Runtime error	1948 KB	Execution killed because of forbidden syscall gettid (186)
12	Incorrect	1944 KB	Output isn't correct
13	Incorrect	1944 KB	Output isn't correct
14	Incorrect	1944 KB	Output isn't correct
15	Incorrect	1944 KB	Output isn't correct
16	Incorrect	1944 KB	Output isn't correct
17	Correct	1944 KB	Output is correct
18	Correct	1944 KB	Output is correct

Subtask #2
0 / 8.0

#	결과	메모리	Grader output
1	Incorrect	1944 KB	Output isn't correct
2	Runtime error	1948 KB	Execution killed because of forbidden syscall gettid (186)
3	Incorrect	1944 KB	Output isn't correct
4	Incorrect	1944 KB	Output isn't correct
5	Correct	1944 KB	Output is correct
6	Incorrect	1944 KB	Output isn't correct
7	Incorrect	1944 KB	Output isn't correct
8	Incorrect	1944 KB	Output isn't correct
9	Correct	1944 KB	Output is correct
10	Incorrect	1944 KB	Output isn't correct
11	Runtime error	1948 KB	Execution killed because of forbidden syscall gettid (186)
12	Incorrect	1944 KB	Output isn't correct
13	Incorrect	1944 KB	Output isn't correct
14	Incorrect	1944 KB	Output isn't correct
15	Incorrect	1944 KB	Output isn't correct
16	Incorrect	1944 KB	Output isn't correct
17	Correct	1944 KB	Output is correct
18	Correct	1944 KB	Output is correct
19	Incorrect	1944 KB	Output isn't correct
20	Incorrect	1944 KB	Output isn't correct
21	Runtime error	1948 KB	Execution killed because of forbidden syscall gettid (186)
22	Incorrect	1944 KB	Output isn't correct
23	Incorrect	1944 KB	Output isn't correct
24	Incorrect	1944 KB	Output isn't correct
25	Incorrect	1944 KB	Output isn't correct
26	Incorrect	1944 KB	Output isn't correct
27	Correct	1944 KB	Output is correct
28	Incorrect	1944 KB	Output isn't correct
29	Incorrect	1944 KB	Output isn't correct
30	Incorrect	1944 KB	Output isn't correct
31	Incorrect	1944 KB	Output isn't correct
32	Incorrect	1944 KB	Output isn't correct
33	Correct	1944 KB	Output is correct
34	Incorrect	1944 KB	Output isn't correct
35	Correct	1944 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
2	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
3	Correct	0 ms	1944 KB	Output is correct
4	Incorrect	0 ms	2296 KB	Output isn't correct
5	Incorrect	103 ms	13732 KB	Output isn't correct
6	Incorrect	136 ms	23408 KB	Output isn't correct
7	Incorrect	119 ms	23540 KB	Output isn't correct
8	Incorrect	0 ms	1944 KB	Output isn't correct
9	Incorrect	123 ms	21996 KB	Output isn't correct
10	Incorrect	136 ms	22908 KB	Output isn't correct
11	Incorrect	53 ms	9136 KB	Output isn't correct
12	Incorrect	116 ms	23276 KB	Output isn't correct
13	Incorrect	139 ms	23152 KB	Output isn't correct
14	Incorrect	73 ms	12888 KB	Output isn't correct
15	Runtime error	126 ms	23280 KB	Execution killed because of forbidden syscall gettid (186)
16	Incorrect	76 ms	12888 KB	Output isn't correct
17	Incorrect	139 ms	23792 KB	Output isn't correct
18	Incorrect	163 ms	23276 KB	Output isn't correct
19	Incorrect	163 ms	23788 KB	Output isn't correct

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	1944 KB	Output isn't correct
2	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
3	Incorrect	0 ms	1944 KB	Output isn't correct
4	Incorrect	0 ms	1944 KB	Output isn't correct
5	Correct	0 ms	1944 KB	Output is correct
6	Incorrect	0 ms	1944 KB	Output isn't correct
7	Incorrect	0 ms	1944 KB	Output isn't correct
8	Incorrect	0 ms	1944 KB	Output isn't correct
9	Correct	0 ms	1944 KB	Output is correct
10	Incorrect	0 ms	1944 KB	Output isn't correct
11	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
12	Incorrect	0 ms	1944 KB	Output isn't correct
13	Incorrect	0 ms	1944 KB	Output isn't correct
14	Incorrect	0 ms	1944 KB	Output isn't correct
15	Incorrect	0 ms	1944 KB	Output isn't correct
16	Incorrect	0 ms	1944 KB	Output isn't correct
17	Correct	0 ms	1944 KB	Output is correct
18	Correct	0 ms	1944 KB	Output is correct
19	Incorrect	0 ms	1944 KB	Output isn't correct
20	Incorrect	0 ms	1944 KB	Output isn't correct
21	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
22	Incorrect	0 ms	1944 KB	Output isn't correct
23	Incorrect	0 ms	1944 KB	Output isn't correct
24	Incorrect	0 ms	1944 KB	Output isn't correct
25	Incorrect	0 ms	1944 KB	Output isn't correct
26	Incorrect	0 ms	1944 KB	Output isn't correct
27	Correct	0 ms	1944 KB	Output is correct
28	Incorrect	0 ms	1944 KB	Output isn't correct
29	Incorrect	0 ms	1944 KB	Output isn't correct
30	Incorrect	0 ms	1944 KB	Output isn't correct
31	Incorrect	0 ms	1944 KB	Output isn't correct
32	Incorrect	0 ms	1944 KB	Output isn't correct
33	Correct	0 ms	1944 KB	Output is correct
34	Incorrect	0 ms	1944 KB	Output isn't correct
35	Correct	0 ms	1944 KB	Output is correct
36	Incorrect	3 ms	2708 KB	Output isn't correct
37	Incorrect	3 ms	2548 KB	Output isn't correct
38	Incorrect	0 ms	2548 KB	Output isn't correct
39	Incorrect	0 ms	2296 KB	Output isn't correct
40	Runtime error	0 ms	2572 KB	Execution killed because of forbidden syscall gettid (186)
41	Correct	0 ms	2296 KB	Output is correct
42	Incorrect	3 ms	2708 KB	Output isn't correct
43	Incorrect	0 ms	1944 KB	Output isn't correct
44	Incorrect	3 ms	2700 KB	Output isn't correct
45	Incorrect	0 ms	2296 KB	Output isn't correct
46	Incorrect	3 ms	2708 KB	Output isn't correct
47	Incorrect	3 ms	2396 KB	Output isn't correct
48	Incorrect	3 ms	2396 KB	Output isn't correct
49	Incorrect	0 ms	2296 KB	Output isn't correct
50	Incorrect	0 ms	2296 KB	Output isn't correct
51	Incorrect	0 ms	2296 KB	Output isn't correct
52	Incorrect	0 ms	2076 KB	Output isn't correct
53	Correct	0 ms	2296 KB	Output is correct
54	Incorrect	0 ms	2244 KB	Output isn't correct
55	Correct	0 ms	2296 KB	Output is correct

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	0 ms	1944 KB	Output isn't correct
2	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
3	Incorrect	0 ms	1944 KB	Output isn't correct
4	Incorrect	0 ms	1944 KB	Output isn't correct
5	Correct	0 ms	1944 KB	Output is correct
6	Incorrect	0 ms	1944 KB	Output isn't correct
7	Incorrect	0 ms	1944 KB	Output isn't correct
8	Incorrect	0 ms	1944 KB	Output isn't correct
9	Correct	0 ms	1944 KB	Output is correct
10	Incorrect	0 ms	1944 KB	Output isn't correct
11	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
12	Incorrect	0 ms	1944 KB	Output isn't correct
13	Incorrect	0 ms	1944 KB	Output isn't correct
14	Incorrect	0 ms	1944 KB	Output isn't correct
15	Incorrect	0 ms	1944 KB	Output isn't correct
16	Incorrect	0 ms	1944 KB	Output isn't correct
17	Correct	0 ms	1944 KB	Output is correct
18	Correct	0 ms	1944 KB	Output is correct
19	Incorrect	0 ms	1944 KB	Output isn't correct
20	Incorrect	0 ms	1944 KB	Output isn't correct
21	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
22	Incorrect	0 ms	1944 KB	Output isn't correct
23	Incorrect	0 ms	1944 KB	Output isn't correct
24	Incorrect	0 ms	1944 KB	Output isn't correct
25	Incorrect	0 ms	1944 KB	Output isn't correct
26	Incorrect	0 ms	1944 KB	Output isn't correct
27	Correct	0 ms	1944 KB	Output is correct
28	Incorrect	0 ms	1944 KB	Output isn't correct
29	Incorrect	0 ms	1944 KB	Output isn't correct
30	Incorrect	0 ms	1944 KB	Output isn't correct
31	Incorrect	0 ms	1944 KB	Output isn't correct
32	Incorrect	0 ms	1944 KB	Output isn't correct
33	Correct	0 ms	1944 KB	Output is correct
34	Incorrect	0 ms	1944 KB	Output isn't correct
35	Correct	0 ms	1944 KB	Output is correct
36	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
37	Runtime error	0 ms	1948 KB	Execution killed because of forbidden syscall gettid (186)
38	Correct	0 ms	1944 KB	Output is correct
39	Incorrect	0 ms	2296 KB	Output isn't correct
40	Incorrect	103 ms	13732 KB	Output isn't correct
41	Incorrect	136 ms	23408 KB	Output isn't correct
42	Incorrect	119 ms	23540 KB	Output isn't correct
43	Incorrect	0 ms	1944 KB	Output isn't correct
44	Incorrect	123 ms	21996 KB	Output isn't correct
45	Incorrect	136 ms	22908 KB	Output isn't correct
46	Incorrect	53 ms	9136 KB	Output isn't correct
47	Incorrect	116 ms	23276 KB	Output isn't correct
48	Incorrect	139 ms	23152 KB	Output isn't correct
49	Incorrect	73 ms	12888 KB	Output isn't correct
50	Runtime error	126 ms	23280 KB	Execution killed because of forbidden syscall gettid (186)
51	Incorrect	76 ms	12888 KB	Output isn't correct
52	Incorrect	139 ms	23792 KB	Output isn't correct
53	Incorrect	163 ms	23276 KB	Output isn't correct
54	Incorrect	163 ms	23788 KB	Output isn't correct
55	Incorrect	3 ms	2708 KB	Output isn't correct
56	Incorrect	3 ms	2548 KB	Output isn't correct
57	Incorrect	0 ms	2548 KB	Output isn't correct
58	Incorrect	0 ms	2296 KB	Output isn't correct
59	Runtime error	0 ms	2572 KB	Execution killed because of forbidden syscall gettid (186)
60	Correct	0 ms	2296 KB	Output is correct
61	Incorrect	3 ms	2708 KB	Output isn't correct
62	Incorrect	0 ms	1944 KB	Output isn't correct
63	Incorrect	3 ms	2700 KB	Output isn't correct
64	Incorrect	0 ms	2296 KB	Output isn't correct
65	Incorrect	3 ms	2708 KB	Output isn't correct
66	Incorrect	3 ms	2396 KB	Output isn't correct
67	Incorrect	3 ms	2396 KB	Output isn't correct
68	Incorrect	0 ms	2296 KB	Output isn't correct
69	Incorrect	0 ms	2296 KB	Output isn't correct
70	Incorrect	0 ms	2296 KB	Output isn't correct
71	Incorrect	0 ms	2076 KB	Output isn't correct
72	Correct	0 ms	2296 KB	Output is correct
73	Incorrect	0 ms	2244 KB	Output isn't correct
74	Correct	0 ms	2296 KB	Output is correct
75	Incorrect	179 ms	28580 KB	Output isn't correct
76	Incorrect	103 ms	18964 KB	Output isn't correct
77	Incorrect	119 ms	27220 KB	Output isn't correct
78	Incorrect	59 ms	12888 KB	Output isn't correct
79	Correct	76 ms	12836 KB	Output is correct
80	Incorrect	153 ms	28580 KB	Output isn't correct
81	Incorrect	3 ms	2708 KB	Output isn't correct
82	Incorrect	139 ms	27800 KB	Output isn't correct
83	Incorrect	66 ms	12888 KB	Output isn't correct
84	Incorrect	143 ms	28580 KB	Output isn't correct
85	Incorrect	146 ms	19592 KB	Output isn't correct
86	Incorrect	146 ms	19600 KB	Output isn't correct
87	Incorrect	86 ms	12888 KB	Output isn't correct
88	Incorrect	89 ms	12888 KB	Output isn't correct
89	Incorrect	159 ms	28580 KB	Output isn't correct
90	Incorrect	159 ms	28580 KB	Output isn't correct
91	Incorrect	159 ms	28580 KB	Output isn't correct
92	Correct	73 ms	12684 KB	Output is correct
93	Incorrect	153 ms	19588 KB	Output isn't correct
94	Incorrect	153 ms	28580 KB	Output isn't correct
95	Incorrect	156 ms	28580 KB	Output isn't correct

답안 #20494

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