Submission #3784

#	Time	Username	Problem	Language	Result	Execution time	Memory
3784		blmarket	Evaluation (kriii1_E)	C++98	0 / 1	60 ms	4136 KiB

E

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <numeric>
#include <iterator>
#include <queue>
#include <set>
#include <map>
#include <vector>

#define mp make_pair
#define pb push_back
#define sqr(x) ((x)*(x))
#define foreach(it,c) for(typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int,int> PII;

template<typename T> int size(const T &a) { return a.size(); } 

struct predict_t {
    PII xrange;
    PII yrange;
    int value;

    bool operator<(const predict_t &rhs) const {
        return xrange < rhs.xrange;
    }
};

vector<int> xs;
vector<int> ys;
map<int, vector<pair<PII, int> > > cmds;
int N;
int cur_row[524230];

void go(int pos, int left, int right, int a, int b, int c) {
    // cout << pos << " " << left << " " << right << " = " << cur_row[pos] << " " << a << b << c << endl;
    int mid = (left + right) / 2;
    if(cur_row[pos] == -1) {
        go(pos*2, left, mid, a,b,c);
        go(pos*2+1, mid, right, a,b,c);
        if(cur_row[pos*2] == cur_row[pos*2+1]) {
            cur_row[pos] = cur_row[pos*2];
        }
        return;
    }
    if(right <= a) return;
    if(b <= left) return;
    if(a <= left && right <= b) {
        cur_row[pos] += c;
        return;
    }
    cur_row[pos*2] = cur_row[pos*2+1] = cur_row[pos];
    cur_row[pos] = -1;
    go(pos*2, left, mid,a,b,c);
    go(pos*2+1, mid, right,a,b,c);
}

void add_to(int a, int b, int c) {
    go(1, 0, 262144, a,b,c);
}

long long traverse(int pos, int left, int right) {
    int mid = (left + right) / 2;
    long long ret = 0;
    if(cur_row[pos] == -1) {
        ret += traverse(pos*2, left, mid);
        ret += traverse(pos*2+1, mid, right);
        if( ret > 1000000007LL) {
            ret -= 1000000007LL;
        }
        return ret;
    }
    ret = cur_row[pos] * cur_row[pos];
    ret %= 1000000007LL;
    if(ret == 0) return ret;
    ret *= (ys[right] - ys[left]);
    // cout << ys[right] - ys[left] << " " << ret << endl;
    ret %= 1000000007LL;
    // cout << ret << endl;
    return ret;
}

int main(void)
{
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        int a,b,c,d,e;
        scanf("%d %d %d %d %d",&a,&b,&c,&d,&e);
        c++; d++;
        ys.pb(b); ys.pb(d);
        cmds[a].pb(mp(mp(b,d), e));
        cmds[c].pb(mp(mp(b,d), -e));
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    long long ret = 0;
    int px = -1;
    cur_row[1] = 0;

    foreach(it, cmds) {
        long long area = traverse(1,0,262144);
        area *= (it->first - px);
        area %= 1000000007LL;
        // cout << area << endl;
        ret += area;
        if( ret > 1000000007LL) {
            ret -= 1000000007LL;
        }
        vector<pair<PII, int> > &now = it->second;
        for(int i=0;i<size(now);i++) {
            pair<PII, int> &topic = now[i];
            int y1 = lower_bound(ys.begin(), ys.end(), topic.first.first) - ys.begin();
            int y2 = lower_bound(ys.begin(), ys.end(), topic.first.second) - ys.begin();

            add_to(y1, y2, topic.second);
            // for(int j=y1;j<y2;j++) cur_row[j] += topic.second;
        }
        px = it->first;
    }
    cout << ret << endl;
}

• Subtask 1: 0 / 1