oj.uz

Submission #22111

# Submission time Handle Problem Language Result Execution time Memory
22111 2017-04-29T10:16:04 Z sgc109(#1015, sgc109) None (KRIII5P_3) C++11
2 / 7
 386 ms 28768 KB 
#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;	
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;

int N;
set<ll> st;
vll range;
vl comp;
ll t[800003];
ll pow2[100003];
int size;
vll v;
void update(int pos, int v){
	while(pos <= size){
		t[pos] += v;
		pos += pos&-pos;
	}
}

ll query(int pos){
	ll ret = 0;
	while(pos > 0){
		ret += t[pos];
		pos -= pos&-pos;
	}
	return ret;
}

bool cmp(pll& A, pll& B){
	if(A.second != B.second) return A.second < B.second;
	return A.first < B.first;
}

int main() {
	inp1(N);
	int cnt = 0;
	FOR(i,N){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		if(a>=b) {
			cnt++;
			continue;
		}
		st.insert(a), st.insert(b);
		range.pb({a,b});
	}
	N-=cnt;
	for(auto it = st.begin() ; it != st.end(); it++){
		comp.pb((*it));
	}
	size = sz(comp);

	FOR(i,N){
		ll& a = range[i].first;
		ll& b = range[i].second;
		a = lower_bound(all(comp),a) - comp.begin() + 1;
		b = lower_bound(all(comp),b) - comp.begin() + 1;
		v.pb({a,1});
		v.pb({b,-1});
	}
	sort(all(v));
	sort(all(range),cmp);

	pow2[0] = 1;
	FOR(i,100001) pow2[i+1] = (pow2[i] * 2) % MOD;

	ll sum = 0;
	int on = 0;
	FOR(i,sz(v)){
		on += v[i].second;
		if(!on) continue;
		if(i!=sz(v)-1) sum = (sum + (v[i+1].first-v[i].first)*(pow2[on]-1)) % MOD;;
	}

	FOR(i,N) {
		update(range[i].first,1);
	}

	ll ans = 0;

	FOR(i,N){
		update(range[i].first,-1);
		ans = (ans + pow2[query(range[i].second-1)]) % MOD;
	}
	
	printf("%lld %lld",sum, ans);
	return 0;
}

Compilation message

i.cpp: In function 'int main()':
i.cpp:61:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  inp1(N);
         ^
i.cpp:65:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a,&b);
                          ^

Subtask #1
2.0 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 9200 KB Output is partially correct
2 Partially correct 0 ms 9192 KB Output is partially correct
3 Partially correct 0 ms 9192 KB Output is partially correct
4 Partially correct 0 ms 9192 KB Output is partially correct
5 Partially correct 0 ms 9192 KB Output is partially correct
6 Partially correct 6 ms 10172 KB Output is partially correct
7 Partially correct 6 ms 10172 KB Output is partially correct
8 Partially correct 3 ms 10172 KB Output is partially correct
9 Partially correct 6 ms 10172 KB Output is partially correct
10 Partially correct 6 ms 10172 KB Output is partially correct
11 Partially correct 79 ms 17344 KB Output is partially correct
12 Partially correct 83 ms 17344 KB Output is partially correct
13 Partially correct 109 ms 17344 KB Output is partially correct
14 Partially correct 79 ms 17344 KB Output is partially correct
15 Partially correct 76 ms 17344 KB Output is partially correct
16 Partially correct 139 ms 18964 KB Output is partially correct
17 Partially correct 156 ms 18952 KB Output is partially correct
18 Partially correct 156 ms 18980 KB Output is partially correct
19 Partially correct 159 ms 18968 KB Output is partially correct
20 Correct 79 ms 14864 KB Output is correct
21 Partially correct 329 ms 28768 KB Output is partially correct
22 Partially correct 349 ms 28768 KB Output is partially correct
23 Partially correct 386 ms 28768 KB Output is partially correct
24 Partially correct 366 ms 28768 KB Output is partially correct
25 Correct 76 ms 17352 KB Output is correct
26 Partially correct 296 ms 26336 KB Output is partially correct
27 Partially correct 266 ms 24468 KB Output is partially correct
28 Partially correct 209 ms 22204 KB Output is partially correct
29 Partially correct 186 ms 21760 KB Output is partially correct
30 Partially correct 176 ms 21048 KB Output is partially correct
31 Partially correct 169 ms 20584 KB Output is partially correct
32 Partially correct 146 ms 19984 KB Output is partially correct
33 Partially correct 139 ms 17704 KB Output is partially correct
34 Partially correct 103 ms 17472 KB Output is partially correct
35 Partially correct 113 ms 17404 KB Output is partially correct
36 Partially correct 339 ms 28764 KB Output is partially correct
37 Partially correct 333 ms 28768 KB Output is partially correct
38 Partially correct 349 ms 28764 KB Output is partially correct
39 Partially correct 356 ms 28768 KB Output is partially correct
40 Partially correct 343 ms 28768 KB Output is partially correct
41 Partially correct 0 ms 9192 KB Output is partially correct
42 Partially correct 0 ms 9192 KB Output is partially correct
43 Partially correct 3 ms 9616 KB Output is partially correct
44 Partially correct 3 ms 9616 KB Output is partially correct
45 Partially correct 69 ms 17124 KB Output is partially correct
46 Partially correct 66 ms 17124 KB Output is partially correct
47 Partially correct 69 ms 17124 KB Output is partially correct
48 Partially correct 176 ms 25100 KB Output is partially correct
49 Partially correct 176 ms 25100 KB Output is partially correct
50 Partially correct 179 ms 25100 KB Output is partially correct