답안 #22179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22179	2017-04-29T14:47:34 Z	스팟보드CSS가깨져요(#1029, imsifile)	구간들 (KRIII5P_3)	C++	7 / 7	373 ms	91192 KB

i

#include<stdio.h>
#include<algorithm>
#define info(t) ((t)==NULL ? itt(1,0) : ((t)->key))
using namespace std;

typedef long long lld;
const lld mod = 1000000007;

struct itt {
	lld gas, rsum;
	itt(lld gas_=0, lld rsum_=0) : gas(gas_), rsum(rsum_) {}
	itt operator+ (const itt& c) {
		return itt(gas*c.gas % mod, (rsum*c.gas+c.rsum) % mod);
	}
};

struct segtr {
	segtr *l, *r; lld mi, mx;
	itt key;
	segtr() {l=NULL; r=NULL;}
} *itr;

void ins(segtr* t, lld ix){
	lld md = ((t->mi) + (t->mx))/2;
	if(t->mi == t->mx){
		t->key = (t->key) + itt(2,ix);
		return;
	}
	if(ix <= md){
		if(t->l == NULL){
			t->l = new segtr;
			t->l->mi = t->mi;
			t->l->mx = md;
			t->l->key = itt(1,0);
		}
		ins(t->l, ix);
	}
	else{
		if(t->r == NULL){
			t->r = new segtr;
			t->r->mi = md+1;
			t->r->mx = t->mx;
			t->r->key = itt(1,0);
		}
		ins(t->r, ix);
	}
	t->key = info(t->l) + info(t->r);
}

itt getinfo(segtr* t, lld s, lld e){
	if(t == NULL || s > e)return itt(1,0);
	lld md = ((t->mi) + (t->mx))/2;
	if(s == t->mi && e == t->mx) return t->key;
	if(e <= md) return getinfo(t->l, s, e);
	if(s >= md+1) return getinfo(t->r, s, e);
	return getinfo(t->l, s, md) + getinfo(t->r, md+1, e);
}

struct intv {
	lld s, e;
	bool operator< (const intv& c) const {
		if(s == c.s)return e<c.e;
		return s<c.s;
	}
}ba[101010];

int N; lld sum1, sum2;

int main(){
	itr = new segtr;
	itr->mi = 0, itr->mx = 1000000000;

	scanf("%d", &N);
	for(int i=0; i<N; i++)scanf("%lld%lld", &ba[i].s, &ba[i].e);
	sort(ba, ba+N);

	for(int i=0; i<N; i++){
		if(ba[i].s >= ba[i].e) continue;
		itt if1, if2;
		if1 = getinfo(itr, ba[i].e+1, 1000000000);
		if2 = getinfo(itr, ba[i].s+1, ba[i].e);
		ins(itr, ba[i].e);

		lld rs = 0, rcn = if1.gas*if2.gas % mod;
		rs = (if2.rsum + ba[i].e) * if1.gas % mod;
		rs -= rcn * ba[i].s % mod;
		rs %= mod;
		if(rs < 0)rs += mod;
		sum1 += rs; sum1 %= mod;
		sum2 += rcn % mod; sum2 %= mod;
	}
	printf("%lld %lld\n", sum1, sum2);
	return 0;
}

Compilation message

i.cpp: In function 'int main()':
i.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
i.cpp:74:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++)scanf("%lld%lld", &ba[i].s, &ba[i].e);
                                                             ^

Subtask #1

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2752 KB	Output is correct
2	Correct	0 ms	2752 KB	Output is correct
3	Correct	0 ms	2752 KB	Output is correct
4	Correct	0 ms	2752 KB	Output is correct
5	Correct	0 ms	2752 KB	Output is correct
6	Correct	13 ms	2752 KB	Output is correct
7	Correct	13 ms	2752 KB	Output is correct
8	Correct	13 ms	2752 KB	Output is correct
9	Correct	13 ms	2752 KB	Output is correct
10	Correct	13 ms	2752 KB	Output is correct
11	Correct	146 ms	2884 KB	Output is correct
12	Correct	146 ms	2884 KB	Output is correct
13	Correct	146 ms	2884 KB	Output is correct
14	Correct	149 ms	2884 KB	Output is correct
15	Correct	173 ms	2884 KB	Output is correct
16	Correct	169 ms	50140 KB	Output is correct
17	Correct	173 ms	50008 KB	Output is correct
18	Correct	153 ms	50272 KB	Output is correct
19	Correct	176 ms	50140 KB	Output is correct
20	Correct	99 ms	3940 KB	Output is correct
21	Correct	329 ms	91192 KB	Output is correct
22	Correct	293 ms	91192 KB	Output is correct
23	Correct	329 ms	91192 KB	Output is correct
24	Correct	299 ms	91192 KB	Output is correct
25	Correct	133 ms	2752 KB	Output is correct
26	Correct	336 ms	70336 KB	Output is correct
27	Correct	366 ms	56212 KB	Output is correct
28	Correct	363 ms	39976 KB	Output is correct
29	Correct	373 ms	34696 KB	Output is correct
30	Correct	363 ms	28756 KB	Output is correct
31	Correct	329 ms	21760 KB	Output is correct
32	Correct	316 ms	13312 KB	Output is correct
33	Correct	289 ms	8428 KB	Output is correct
34	Correct	256 ms	5260 KB	Output is correct
35	Correct	239 ms	4072 KB	Output is correct
36	Correct	329 ms	91192 KB	Output is correct
37	Correct	306 ms	91192 KB	Output is correct
38	Correct	309 ms	91192 KB	Output is correct
39	Correct	306 ms	91192 KB	Output is correct
40	Correct	346 ms	91192 KB	Output is correct
41	Correct	0 ms	3280 KB	Output is correct
42	Correct	0 ms	3676 KB	Output is correct
43	Correct	6 ms	4336 KB	Output is correct
44	Correct	3 ms	6316 KB	Output is correct
45	Correct	86 ms	27700 KB	Output is correct
46	Correct	56 ms	2752 KB	Output is correct
47	Correct	86 ms	49744 KB	Output is correct
48	Correct	146 ms	33508 KB	Output is correct
49	Correct	113 ms	2752 KB	Output is correct
50	Correct	176 ms	90664 KB	Output is correct