oj.uz

Submission #22097

# Submission time Handle Problem Language Result Execution time Memory
22097 2017-04-29T08:50:11 Z 쀼쀼~(#1017, cki86201) None (KRIII5P_3) C++11
0 / 7
 289 ms 12248 KB 
#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;
	rep(i, N){
		scanf("%d%d", S+i, D+i);
		v.pb(pii(S[i], 1));
		v.pb(pii(D[i], -1));
		xs[xz++] = S[i];
		xs[xz++] = D[i];
	}
	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

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:94:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", S+i, D+i);
                          ^

Subtask #1
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8072 KB Output is correct
2 Correct 0 ms 8072 KB Output is correct
3 Correct 0 ms 8072 KB Output is correct
4 Correct 0 ms 8072 KB Output is correct
5 Correct 0 ms 8072 KB Output is correct
6 Correct 9 ms 8664 KB Output is correct
7 Correct 6 ms 8664 KB Output is correct
8 Correct 6 ms 8664 KB Output is correct
9 Correct 3 ms 8664 KB Output is correct
10 Correct 3 ms 8664 KB Output is correct
11 Correct 96 ms 12248 KB Output is correct
12 Correct 106 ms 12248 KB Output is correct
13 Correct 106 ms 12248 KB Output is correct
14 Correct 106 ms 12248 KB Output is correct
15 Correct 103 ms 12248 KB Output is correct
16 Incorrect 289 ms 12248 KB Output isn't correct
17 Halted 0 ms 0 KB -