oj.uz

Submission #19100

# Submission time Handle Problem Language Result Execution time Memory
19100 2016-02-18T09:58:36 Z cki86201 Evaluation (kriii1_E) C++
1 / 1
 416 ms 11724 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
 
using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
 
const int MOD = 1e9 + 7;
 
struct line{
    int x, y1, y2, v;
    line(){}
    line(int x,int y1,int y2,int v):x(x), y1(y1), y2(y2), v(v){}
    bool operator<(const line &l)const{
        return x < l.x;
    }
}L[200020];
 
int in[100020][5];
int v[200020];
 
int Tx[530000], Tu[530000];
 
void Do(int rt,int s,int d,int upd){
    int len = (v[d] - v[s-1]);
    Tx[rt] = (Tx[rt] + (ll)len * upd) % MOD;
    Tu[rt] = (Tu[rt] + upd) % MOD;
}
 
void pushdown(int rt,int s,int d){
    int m = (s+d)>>1;
    Do(rt<<1, s, m, Tu[rt]);
    Do(rt<<1|1, m+1, d, Tu[rt]);
    Tu[rt] = 0;
}
 
int update(int rt,int s,int d,int l,int r,int upd){
    if(l <= s && d <= r){
        int tmp = Tx[rt];
        Do(rt, s, d, upd);
        return tmp;
    }
    if(Tu[rt])pushdown(rt, s, d);
    int m = (s+d)>>1;
    int res = 0;
    if(l<=m){
        res += update(rt+rt, s, m, l, r, upd);
    }
    if(m<r){
        res += update(rt+rt+1, m+1, d, l, r, upd);
    }
    Tx[rt] = (Tx[rt<<1] + Tx[rt<<1|1]) % MOD;
    return res % MOD;
}
 
int main(){
    int n; scanf("%d", &n);
    rep(i, n){
        rep(j, 5)scanf("%d", in[i] + j);
        v[i+i] = in[i][1];
        v[i+i+1] = in[i][3] + 1;
        L[i+i].y1 = L[i+i+1].y1 = in[i][1];
        L[i+i].y2 = L[i+i+1].y2 = in[i][3] + 1;
    }
    sort(v, v+n+n);
    int m = (int)(unique(v, v+n+n) - v);
    for(int i=0;i<n+n;i++){
        L[i].y1 = (int)(lower_bound(v, v+m, L[i].y1) - v);
        L[i].y2 = (int)(lower_bound(v, v+m, L[i].y2) - v);
    }
    for(int i=0;i<n;i++){
        L[i+i].x = in[i][0];
        L[i+i+1].x = in[i][2] + 1;
        L[i+i].v = in[i][4];
        L[i+i+1].v = -in[i][4];
    }
    sort(L, L+n+n);
    ll ans = 0, now = 0;
    for(int i=0;i<n+n;i++){
        int lv = L[i].y1;
        int rv = L[i].y2;
        if(i){
            ans = (ans + now * (L[i].x - L[i-1].x)) % MOD;
        }
        now += (ll)(v[rv] - v[lv]) * L[i].v * L[i].v;
        now %= MOD;
        now += 2LL * (MOD + L[i].v) * update(1, 1, m-1, lv+1, rv, MOD+L[i].v);
        now %= MOD;
    }
    printf("%lld", ans);
    return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11724 KB Output is correct
2 Correct 0 ms 11724 KB Output is correct
3 Correct 0 ms 11724 KB Output is correct
4 Correct 0 ms 11724 KB Output is correct
5 Correct 0 ms 11724 KB Output is correct
6 Correct 0 ms 11724 KB Output is correct
7 Correct 0 ms 11724 KB Output is correct
8 Correct 2 ms 11724 KB Output is correct
9 Correct 4 ms 11724 KB Output is correct
10 Correct 0 ms 11724 KB Output is correct
11 Correct 16 ms 11724 KB Output is correct
12 Correct 20 ms 11724 KB Output is correct
13 Correct 21 ms 11724 KB Output is correct
14 Correct 30 ms 11724 KB Output is correct
15 Correct 27 ms 11724 KB Output is correct
16 Correct 147 ms 11724 KB Output is correct
17 Correct 207 ms 11724 KB Output is correct
18 Correct 268 ms 11724 KB Output is correct
19 Correct 397 ms 11724 KB Output is correct
20 Correct 416 ms 11724 KB Output is correct