| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 5129 |
2014-02-10T09:02:51 Z |
ainta |
Evaluation (kriii1_E) |
C++ |
|
280 ms |
14776 KB |
#include<stdio.h>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, Y[200010];
long long SS, Mod = 1000000007, Sum, res;
struct YY{
int y, num;
bool operator <(const YY &p)const{
return y < p.y;
}
}p[201000];
struct Seg{
int x, y1, y2, p;
bool operator <(const Seg &p)const{
return x < p.x;
}
}w[201000];
struct SegTree{
int K;
long long S;
}IT[SZ * 2 + 1];
void spread(int node, long long K, int b, int e, int m){
int c1 = node * 2, c2 = node * 2 + 1;
IT[c1].K += K, IT[c2].K += K;
IT[c1].S += K*(Y[m + 1] - Y[b]);
IT[c2].S += K*(Y[e + 1] - Y[m + 1]);
IT[node].K = 0;
}
void Add(int node, int b, int e, int s, int l, long long x){
if (b == s && e == l){
Sum += IT[node].S;
IT[node].K += x;
IT[node].S += x*(Y[e + 1] - Y[b]);
return;
}
int m = (b + e) >> 1;
if (IT[node].K)spread(node, IT[node].K, b, e, m);
if (s <= m)Add(node * 2, b, m, s, min(l, m), x);
if (l > m)Add(node * 2 + 1, m + 1, e, max(m + 1, s), l, x);
IT[node].S = IT[node * 2].S + IT[node * 2 + 1].S;
}
int main(){
int i, y1, y2, c = 0;
scanf("%d", &n);
for (i = 0; i < n; i++){
scanf("%d%d%d%d%d", &w[i * 2].x, &p[i * 2].y, &w[i * 2 + 1].x, &p[i * 2 + 1].y, &w[i * 2].p);
w[i * 2 + 1].x++, w[i * 2 + 1].p = -w[i * 2].p;
p[i * 2 + 1].y++;
p[i * 2].num = i * 2, p[i * 2 + 1].num = i * 2 + 1;
}
sort(p, p + 2 * n);
for (i = 0; i < 2 * n; i++){
if (!i || p[i].y != p[i - 1].y)Y[++c] = p[i].y;
if (p[i].num & 1)w[p[i].num].y2 = w[p[i].num ^ 1].y2 = c;
else w[p[i].num].y1 = w[p[i].num ^ 1].y1 = c;
}
sort(w, w + 2 * n);
for (i = 0; i < 2 * n; i++){
Sum = 0;
Add(1, 1, SZ, w[i].y1, w[i].y2 - 1, w[i].p);
Sum %= Mod;
SS = SS + Sum * 2 * w[i].p + (long long)(Y[w[i].y2] - Y[w[i].y1])*w[i].p*w[i].p;
if (SS < 0)SS += (-SS) / Mod*Mod + Mod;
SS %= Mod;
if (w[i].x != w[i + 1].x)res = (res + SS*(w[i + 1].x - w[i].x)) % Mod;
}
printf("%lld\n", res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 2 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 3 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 4 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 5 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 6 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 7 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 8 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 9 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 10 |
Correct |
0 ms |
14776 KB |
Output is correct |
| 11 |
Correct |
12 ms |
14776 KB |
Output is correct |
| 12 |
Correct |
16 ms |
14776 KB |
Output is correct |
| 13 |
Correct |
16 ms |
14776 KB |
Output is correct |
| 14 |
Correct |
20 ms |
14776 KB |
Output is correct |
| 15 |
Correct |
24 ms |
14776 KB |
Output is correct |
| 16 |
Correct |
136 ms |
14776 KB |
Output is correct |
| 17 |
Correct |
168 ms |
14776 KB |
Output is correct |
| 18 |
Correct |
188 ms |
14776 KB |
Output is correct |
| 19 |
Correct |
268 ms |
14776 KB |
Output is correct |
| 20 |
Correct |
280 ms |
14776 KB |
Output is correct |
