Submission #22179

#	Time	Username	Problem	Language	Result	Execution time	Memory
22179		스팟보드CSS가깨져요 (#42)	구간들 (KRIII5P_3)	C++98	7 / 7	373 ms	91192 KiB

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 (stderr)

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 / 7