Submission #3429

#	Time	Username	Problem	Language	Result	Execution time	Memory
3429		blmarket	Evaluation (kriii1_E)	C++98	0 / 1	2000 ms	4700 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[200005];

int main(void)
{
    memset(cur_row, 0, sizeof(cur_row));
    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;
    foreach(it, cmds) {
        for(int i=0;i<size(ys);i++) {
            if(cur_row[i]) {
                long long area = (long long)(it->first - px) * (ys[i+1] - ys[i]);
                area %= 1000000007LL;
                area *= cur_row[i];
                area %= 1000000007LL;
                ret += area * cur_row[i];
                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();
            for(int j=y1;j<y2;j++) cur_row[j] += topic.second;
        }
        px = it->first;
    }
    cout << ret << endl;
}

• Subtask 1: 0 / 1