Submission #22096

#	Time	Username	Problem	Language	Result	Execution time	Memory
22096		삼*전자 그린픽스 (#42)	구간들 (KRIII5P_3)	C++98	2 / 7	129 ms	9312 KiB

i

#include<stdio.h>
#include<algorithm>
#define M 1000000007
#define I 262144
using namespace std;
typedef pair<int, int> pii;
int n;
int x[2*I];
int xl;
pii a[I];

long long int tw[I];

void input() {
	int i, j, k, l;
	xl = 0;
	x[xl++] = 0;
	x[xl++] = M;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d %d", &a[i].second, &a[i].first);
		if (a[i].second >= a[i].first) {
			n--;
			i--;
			continue;
		}
		x[xl++] = a[i].first;
		x[xl++] = a[i].second;
	}
	sort(a, a + n);
	sort(x, x + xl);
	xl = unique(x, x + xl) - x;
	for (i = 0; i < n; i++) {
		//change first and second
		k = a[i].first;
		a[i].first = lower_bound(x, x + xl, a[i].second) - x;
		a[i].second = lower_bound(x, x + xl, k) - x;
	}
	tw[0] = 1;
	for (i = 1; i < I; i++)
		tw[i] = (tw[i - 1] * 2) % M;
}
long long int resa, resb;
int ms[2 * I];
int get_ms(int dep, int ql, int qr, int ll, int rr)
{
	if (qr < ll || rr < ql) return 0;
	if (ql <= ll && rr <= qr) return ms[dep];
	return get_ms(dep * 2, ql, qr, ll, (ll + rr) / 2) + get_ms(dep * 2 + 1, ql, qr, (ll + rr) / 2 + 1, rr);
}
void update_ms(int i)
{
	i += I;
	ms[i]++;
	i /= 2;
	while (i > 0) {
		ms[i] = ms[i * 2] + ms[i * 2 + 1];
		i /= 2;
	}
}
long long int func(int xi) {
	int i, j, k;
	// return 2^s0 + 2^s1 + .. +2^sx[i] - 1
	long long int res = 0;
	//naive solution
	if (0)
	{
		for (i = 1; i < xi; i++) {
			long long int cur;
			long long int dist = x[i + 1] - x[i];
			long long int val = get_ms(1, 0, i, 0, I - 1);
			cur = (dist * tw[val]) % M;

			res = (res + cur);
		}
	}
	return res;
}
void process() {
	int i, j, k, l;
	/*
	resa += 
	 (2^sq - 1) * q -
	 {
	 (2^sp - 1) * p
	 (2^sp+1 - 2^sp) * (p+1)
	 ...
	 (2^sq-1 - 2^sq-2) * (q-1)
	 (2^sq - 2^sq-1) * q
	 }
	 =
	 p - q
	 + 2^sp + 2^sp+! + ... + 2^sq-2 + 2^sq-1

	resb +=
	 (2^sq-1 - 1) + 1
	 */
	resa = 0;
	resb = 0;
	long long int cura, curb;
	for (i = n - 1; i >= 0; i--) {
		cura = 0;
		cura = (cura + func(a[i].second)) % M;
		cura = (cura - func(a[i].first) + M) % M;

		k = get_ms(1, 0, a[i].second - 1, 0, I - 1);
		curb = tw[k];

		resa = (resa + cura) % M;
		resb = (resb + curb) % M;
//		printf("%d %d --> %lld %lld\n", x[a[i].first], x[a[i].second], cura, curb);

		update_ms(a[i].first);
	}
	printf("%lld %lld\n", resa, resb);
}
int main() {
	int i, j, k, l;
	input();
	process();
	return 0;
}

Compilation message (stderr)

i.cpp: In function 'void input()':
i.cpp:15:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
i.cpp:15:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
i.cpp: In function 'long long int func(int)':
i.cpp:62:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k;
         ^
i.cpp:62:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
i.cpp: In function 'void process()':
i.cpp:80:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
i.cpp:80:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
i.cpp: In function 'int main()':
i.cpp:118:6: warning: unused variable 'i' [-Wunused-variable]
  int i, j, k, l;
      ^
i.cpp:118:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
i.cpp:118:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, l;
            ^
i.cpp:118:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
i.cpp: In function 'void input()':
i.cpp:19:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
i.cpp:21:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i].second, &a[i].first);
                                            ^

• Subtask 1: 2 / 7