Submission #3429

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3429	2013-08-31T05:45:48 Z	blmarket	Evaluation (kriii1_E)	C++	0 / 1	2000 ms	4700 KB

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2460 KB	Output is correct
2	Correct	0 ms	2460 KB	Output is correct
3	Correct	0 ms	2460 KB	Output is correct
4	Correct	0 ms	2460 KB	Output is correct
5	Correct	0 ms	2460 KB	Output is correct
6	Correct	0 ms	2460 KB	Output is correct
7	Correct	8 ms	2460 KB	Output is correct
8	Correct	32 ms	2592 KB	Output is correct
9	Correct	44 ms	2592 KB	Output is correct
10	Correct	44 ms	2592 KB	Output is correct
11	Correct	8 ms	2868 KB	Output is correct
12	Correct	32 ms	2988 KB	Output is correct
13	Correct	848 ms	3552 KB	Output is correct
14	Execution timed out	2000 ms	4700 KB	Program timed out
15	Halted	0 ms	0 KB	-