Submission #22106

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22106	2017-04-29T10:06:23 Z	sgc109(#1015, sgc109)	None (KRIII5P_3)	C++11	0 / 7	319 ms	28768 KB

i

#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);
	FOR(i,N){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		st.insert(a), st.insert(b);
		range.pb({a,b});
	}
	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:64: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

0.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	6 ms	10172 KB	Output is partially correct
9	Partially correct	6 ms	10172 KB	Output is partially correct
10	Partially correct	0 ms	10172 KB	Output is partially correct
11	Partially correct	76 ms	17344 KB	Output is partially correct
12	Partially correct	83 ms	17344 KB	Output is partially correct
13	Partially correct	76 ms	17344 KB	Output is partially correct
14	Partially correct	73 ms	17344 KB	Output is partially correct
15	Partially correct	79 ms	17344 KB	Output is partially correct
16	Incorrect	319 ms	28768 KB	Output isn't correct
17	Halted	0 ms	0 KB	-