oj.uz

Submission #235183

# Submission time Handle Problem Language Result Execution time Memory
235183 2020-05-27T08:45:52 Z NONAME Usmjeri (COCI17_usmjeri) C++17
28 / 140
 576 ms 9080 KB 
#include <bits/stdc++.h>
#define sz(x) int(x.size())
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
#define el '\n'
#define base ll(1e9 + 7)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

void add(ll &x, ll y) { (x += y) %= base; }

void mul(ll &x, ll y) { (x *= y) %= base; }

ll bin_pow(ll x, ll st) {
	ll rs = 1;
	
	while (st > 0) {
		if (st & 1)
			mul(rs, x);
		
		mul(x, x);
		st >>= 1;	
	}
	
	return rs;	
}

ll ans;
int n, q, l0, r0, lst;
vector <pii> v, res;

int main() {
	cin >> n >> q;
	
	for (int i = 0; i < n - 1; i++) {
		int x;
		cin >> x >> x;	
	}
	
	for (int i = 0; i < q; i++) {
		int l, r;
		
		cin >> l >> r;
		l--; r--;
		
		v.pb(mp(l, r));	
	}
	
	sort(v.begin(), v.end());
	
	l0 = v[0].ft;
	r0 = v[0].sd;
	
	for (int i = 1; i < q; i++) {
		int l = v[i].ft, r = v[i].sd;
		
		if (l <= r0) r0 = max(r0, r);
			else {
				res.pb(mp(l0, r0));
				l0 = l, r0 = r;	
			}
	}
	
	res.pb(mp(l0, r0));
	
	lst = 0;
	
	for (int i = 0; i < sz(res); i++) {
		add(ans, res[i].ft - lst);
		
		lst = res[i].sd;
	}
	
//	for (int i = 0; i < sz(res); i++)
//		cerr << res[i].ft << ' ' << res[i].sd << el;
	
	cout << bin_pow(2, sz(res) + ans + ((n - 1) - res.back().sd));
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 2668 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 4452 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 573 ms 8972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 553 ms 4548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 567 ms 9080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 576 ms 8940 KB Output isn't correct
2 Halted 0 ms 0 KB -