Submission #22099

#	Time	Username	Problem	Language	Result	Execution time	Memory
22099		쀼쀼~ (#42)	구간들 (KRIII5P_3)	C++11	7 / 7	303 ms	12248 KiB

i

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;
typedef long double ldouble;

const int MOD = 1e9 + 7;
int P[100010], N;

int xs[200020], xz;
int S[100010], D[100010];

int T[1<<19];
int C[1<<19];

void pushdown(int rt){
	if(C[rt] != 1){
		T[rt<<1] = (ll)T[rt<<1] * C[rt] % MOD;
		C[rt<<1] = (ll)C[rt<<1] * C[rt] % MOD;
		T[rt<<1|1] = (ll)T[rt<<1|1] * C[rt] % MOD;
		C[rt<<1|1] = (ll)C[rt<<1|1] * C[rt] % MOD;
		C[rt] = 1;
	}
}

void add(int rt, int l, int r, int x, int v){
	if(l == r){
		T[rt] = (T[rt] + v) % MOD;
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	if(x <= m)add(rt<<1, l, m, x, v);
	else add(rt<<1|1, m+1, r, x, v);
	T[rt] = (T[rt<<1] + T[rt<<1|1]) % MOD;
}

void update(int rt, int l, int r, int s, int d, int v){
	if(s <= l && r <= d){
		T[rt] = (ll)T[rt] * v % MOD;
		C[rt] = (ll)C[rt] * v % MOD;
		return;
	}
	pushdown(rt);
	int m = (l + r) >> 1;
	if(s <= m) update(rt<<1, l, m, s, d, v);
	if(m < d) update(rt<<1|1, m+1, r, s, d, v);
	T[rt] = (T[rt<<1] + T[rt<<1|1]) % MOD;
}

int read(int rt, int l, int r, int s, int d){
	if(s <= l && r <= d){
		return T[rt];
	}
	pushdown(rt);
	int m = (l + r) >> 1, res = 0;
	if(s <= m) res = (res + read(rt<<1, l, m, s, d)) % MOD;
	if(m < d) res = (res + read(rt<<1|1, m+1, r, s, d)) % MOD;
	T[rt] = (T[rt<<1] + T[rt<<1|1]) % MOD;
	return res;
}

void solve(){
	scanf("%d", &N);
	vector <pii> v;
	int tn = 0;
	rep(i, N){
		scanf("%d%d", S+tn, D+tn);
		if(S[tn] >= D[tn]) continue;
		v.pb(pii(S[tn], 1));
		v.pb(pii(D[tn], -1));
		xs[xz++] = S[tn];
		xs[xz++] = D[tn];
		++tn;
	}
	N = tn;
	sort(all(v));
	sort(xs, xs+xz);
	xz = (int)(unique(xs, xs+xz) - xs);
	vector <pii> V;
	rep(i, N){
		int x = (int)(lower_bound(xs, xs+xz, S[i]) - xs);
		int y = (int)(lower_bound(xs, xs+xz, D[i]) - xs);
		V.pb(pii(x, y));
	}
	P[1] = 1;
	for(int i=2;i<=N;i++)P[i] = (2 * P[i-1] + 1) % MOD;
	ll ans = 0;
	for(int i=0, c=0;i<sz(v);i++){
		c += v[i].Se;
		if(i+1 < sz(v) && v[i].Fi != v[i+1].Fi){
			ans = (ans + (ll)(v[i+1].Fi - v[i].Fi) * P[c]) % MOD;
		}
	}
	printf("%lld ", ans);
	sort(all(V));
	rep(i, 1<<19)C[i] = 1;
	for(int i=0;i<sz(V);i++){
		int t = read(1, 0, xz - 1, V[i].Se, xz - 1);
		add(1, 0, xz - 1, V[i].Se, (t + 1) % MOD);
		update(1, 0, xz - 1, V[i].Fi + 1, V[i].Se - 1, 2);
	}
	printf("%d\n", read(1, 0, xz - 1, 0, xz - 1));
}

int main(){
	int Tc = 1; //scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Compilation message (stderr)

i.cpp: In function 'void solve()':
i.cpp:91:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
i.cpp:95:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", S+tn, D+tn);
                            ^

• Subtask 1: 7 / 7