| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22095 | 2017-04-29T08:24:54 Z | 삼*전자 그린픽스(#1005, pichulia) | None (KRIII5P_3) | C++ | 109 ms | 6776 KB |
#include<stdio.h>
#include<algorithm>
#define M 1000000007
#define I 262144
using namespace std;
typedef pair<int, int> pii;
int n;
int x[200009];
int xl;
pii a[100009];
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);
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
*/
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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 0 ms | 6776 KB | Output is partially correct |
| 2 | Partially correct | 3 ms | 6776 KB | Output is partially correct |
| 3 | Partially correct | 3 ms | 6776 KB | Output is partially correct |
| 4 | Partially correct | 3 ms | 6776 KB | Output is partially correct |
| 5 | Partially correct | 3 ms | 6776 KB | Output is partially correct |
| 6 | Partially correct | 6 ms | 6776 KB | Output is partially correct |
| 7 | Partially correct | 9 ms | 6776 KB | Output is partially correct |
| 8 | Partially correct | 6 ms | 6776 KB | Output is partially correct |
| 9 | Partially correct | 6 ms | 6776 KB | Output is partially correct |
| 10 | Partially correct | 9 ms | 6776 KB | Output is partially correct |
| 11 | Partially correct | 69 ms | 6776 KB | Output is partially correct |
| 12 | Partially correct | 76 ms | 6776 KB | Output is partially correct |
| 13 | Partially correct | 59 ms | 6776 KB | Output is partially correct |
| 14 | Partially correct | 76 ms | 6776 KB | Output is partially correct |
| 15 | Partially correct | 66 ms | 6776 KB | Output is partially correct |
| 16 | Incorrect | 109 ms | 6776 KB | Output isn't correct |
| 17 | Halted | 0 ms | 0 KB | - |