| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22098 | 삼*전자 그린픽스 (#42) | 구간들 (KRIII5P_3) | C++98 | 376 ms | 16480 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||