Submission #235182

#	Time	Username	Problem	Language	Result	Execution time	Memory
235182		NONAME	Usmjeri (COCI17_usmjeri)	C++17	0 / 140	575 ms	9108 KiB

usmjeri

#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)) %= 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 = 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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14