| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 22098 |
2017-04-29T08:53:00 Z |
삼*전자 그린픽스(#1005, pichulia) |
구간들 (KRIII5P_3) |
C++ |
|
376 ms |
16480 KB |
#include<stdio.h>
#include<algorithm>
#define M 1000000007
#define I 262144
using namespace std;
typedef pair<int, int> pii;
int n;
int x[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];
long long int md[2 * I];
long long int ml[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 get_md(int dep, int ql, int qr, int ll, int rr) {
if (qr < ll || rr < ql) return 0;
if (ql <= ll && rr <= qr) return (md[dep] * tw[ml[dep]])%M;
if (ml[dep]) {
ml[dep * 2] += ml[dep];
ml[dep * 2 + 1] += ml[dep];
md[dep] = (md[dep] * tw[ml[dep]]) % M;
ml[dep] = 0;
}
long long int cur = (get_md(dep * 2, ql, qr, ll, (ll + rr) / 2) + get_md(dep * 2 + 1, ql, qr, (ll + rr) / 2 + 1, rr))%M;
// cur = (cur * tw[ml[dep]]) % M;
return cur;
}
void update_from_me(int dep) {
int i = dep;
i /= 2;
while (i > 0) {
long long int cur = 0;
cur = (cur + md[2 * i] * tw[ml[i * 2]]) % M;
cur = (cur + md[2 * i + 1] * tw[ml[i * 2 + 1]]) % M;
md[i] = cur;
i /= 2;
}
}
void update_md(int dep, int ql, int qr, int ll, int rr, int k) {
if (qr < ll || rr < ql) return;
if (ql <= ll && rr <= qr)
{
ml[dep] += k;
update_from_me(dep);
return;
}
int mid = (ll + rr) / 2;
update_md(dep * 2, ql, qr, ll, mid, k);
update_md(dep * 2+1, ql, qr, mid+1, rr, k);
}
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 = 0; 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);
}
}
else
{
res = get_md(1, 0, xi - 1, 0, I - 1);
}
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
}
+q-p
=
2^sp + 2^sp+! + ... + 2^sq-2 + 2^sq-1
resb +=
(2^sq-1 - 1) + 1
*/
resa = 0;
resb = 0;
//init
for (i = 0; i < 2 * I; i++)
{
ml[i] = 0;
ms[i] = 0;
}
for (i = 0; i < xl - 1; i++) {
md[i + I] = x[i + 1] - x[i];
}
for (; i < I; i++) {
md[i + I] = 0;
}
for (i = I - 1; i > 0; i--) {
md[i] = (md[2 * i] + md[2 * i + 1]) % M;
}
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);
update_md(1, a[i].first, I - 1, 0, I - 1, 1);
}
printf("%lld %lld\n", resa, resb);
}
int main() {
int i, j, k, l;
input();
process();
return 0;
}
Compilation message
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:102:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, k;
^
i.cpp:102:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
i.cpp: In function 'void process()':
i.cpp:124:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, k, l;
^
i.cpp:124:15: warning: unused variable 'l' [-Wunused-variable]
int i, j, k, l;
^
i.cpp: In function 'int main()':
i.cpp:178:6: warning: unused variable 'i' [-Wunused-variable]
int i, j, k, l;
^
i.cpp:178:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, k, l;
^
i.cpp:178:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k, l;
^
i.cpp:178: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);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
16480 KB |
Output is correct |
| 2 |
Correct |
3 ms |
16480 KB |
Output is correct |
| 3 |
Correct |
9 ms |
16480 KB |
Output is correct |
| 4 |
Correct |
6 ms |
16480 KB |
Output is correct |
| 5 |
Correct |
9 ms |
16480 KB |
Output is correct |
| 6 |
Correct |
33 ms |
16480 KB |
Output is correct |
| 7 |
Correct |
33 ms |
16480 KB |
Output is correct |
| 8 |
Correct |
39 ms |
16480 KB |
Output is correct |
| 9 |
Correct |
39 ms |
16480 KB |
Output is correct |
| 10 |
Correct |
29 ms |
16480 KB |
Output is correct |
| 11 |
Correct |
303 ms |
16480 KB |
Output is correct |
| 12 |
Correct |
296 ms |
16480 KB |
Output is correct |
| 13 |
Correct |
296 ms |
16480 KB |
Output is correct |
| 14 |
Correct |
296 ms |
16480 KB |
Output is correct |
| 15 |
Correct |
293 ms |
16480 KB |
Output is correct |
| 16 |
Correct |
166 ms |
16480 KB |
Output is correct |
| 17 |
Correct |
179 ms |
16480 KB |
Output is correct |
| 18 |
Correct |
186 ms |
16480 KB |
Output is correct |
| 19 |
Correct |
159 ms |
16480 KB |
Output is correct |
| 20 |
Correct |
156 ms |
16480 KB |
Output is correct |
| 21 |
Correct |
336 ms |
16480 KB |
Output is correct |
| 22 |
Correct |
323 ms |
16480 KB |
Output is correct |
| 23 |
Correct |
293 ms |
16480 KB |
Output is correct |
| 24 |
Correct |
319 ms |
16480 KB |
Output is correct |
| 25 |
Correct |
286 ms |
16480 KB |
Output is correct |
| 26 |
Correct |
319 ms |
16480 KB |
Output is correct |
| 27 |
Correct |
299 ms |
16480 KB |
Output is correct |
| 28 |
Correct |
323 ms |
16480 KB |
Output is correct |
| 29 |
Correct |
296 ms |
16480 KB |
Output is correct |
| 30 |
Correct |
289 ms |
16480 KB |
Output is correct |
| 31 |
Correct |
299 ms |
16480 KB |
Output is correct |
| 32 |
Correct |
276 ms |
16480 KB |
Output is correct |
| 33 |
Correct |
289 ms |
16480 KB |
Output is correct |
| 34 |
Correct |
263 ms |
16480 KB |
Output is correct |
| 35 |
Correct |
276 ms |
16480 KB |
Output is correct |
| 36 |
Correct |
323 ms |
16480 KB |
Output is correct |
| 37 |
Correct |
306 ms |
16480 KB |
Output is correct |
| 38 |
Correct |
339 ms |
16480 KB |
Output is correct |
| 39 |
Correct |
323 ms |
16480 KB |
Output is correct |
| 40 |
Correct |
333 ms |
16480 KB |
Output is correct |
| 41 |
Correct |
6 ms |
16480 KB |
Output is correct |
| 42 |
Correct |
9 ms |
16480 KB |
Output is correct |
| 43 |
Correct |
9 ms |
16480 KB |
Output is correct |
| 44 |
Correct |
16 ms |
16480 KB |
Output is correct |
| 45 |
Correct |
139 ms |
16480 KB |
Output is correct |
| 46 |
Correct |
106 ms |
16480 KB |
Output is correct |
| 47 |
Correct |
179 ms |
16480 KB |
Output is correct |
| 48 |
Correct |
203 ms |
16480 KB |
Output is correct |
| 49 |
Correct |
243 ms |
16480 KB |
Output is correct |
| 50 |
Correct |
376 ms |
16480 KB |
Output is correct |
