oj.uz

Submission #59643

# Submission time Handle Problem Language Result Execution time Memory
59643 2018-07-22T20:30:34 Z duality Land of the Rainbow Gold (APIO17_rainbow) C++11
47 / 100
 3000 ms 531432 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#include "rainbow.h"

int r,c;
int lx,rx,ly,ry;
struct xNode {
    xNode *l,*r;
    int sum;
    xNode() { l = r = NULL; sum = 0; }
    int query(int s,int e,int qs,int qe) {
        if (s > e) return 0;
        else if ((s > qe) || (e < qs)) return 0;
        else if ((s >= qs) && (e <= qe)) return sum;

        int mid = (s+e) / 2;
        return ((l == NULL) ? 0:l->query(s,mid,qs,qe))+((r == NULL) ? 0:r->query(mid+1,e,qs,qe));
    }
    int update(int s,int e,int ai) {
        if (s == e) {
            sum++;
            return sum;
        }

        int mid = (s+e) / 2;
        if (ai <= mid) {
            if (l == NULL) l = new xNode;
            sum = l->update(s,mid,ai)+((r == NULL) ? 0:r->sum);
        }
        else {
            if (r == NULL) r = new xNode;
            sum = r->update(mid+1,e,ai)+((l == NULL) ? 0:l->sum);
        }
        return sum;
    }
};
struct yNode {
    yNode *l,*r;
    xNode *x;
    yNode() { l = r = NULL; x = new xNode; };
    int query(int sy,int ey,int qys,int qye,int qxs,int qxe) {
        if (sy > ey) return 0;
        else if ((sy > qye) || (ey < qys)) return 0;
        else if ((sy >= qys) && (ey <= qye)) return x->query(0,c,qxs,qxe);

        int mid = (sy+ey) / 2;
        return ((l == NULL) ? 0:l->query(sy,mid,qys,qye,qxs,qxe))+((r == NULL) ? 0:r->query(mid+1,ey,qys,qye,qxs,qxe));
    }
    int update(int sy,int ey,int ay,int ax) {
        if (sy == ey) {
            x->update(0,c,ax);
            return 0;
        }

        int mid = (sy+ey) / 2;
        if (ay <= mid) {
            if (l == NULL) l = new yNode;
            l->update(sy,mid,ay,ax);
        }
        else {
            if (r == NULL) r = new yNode;
            r->update(mid+1,ey,ay,ax);
        }
        x->update(0,c,ax);
        return 0;
    }
};
vpii p1,p2,p3,p4;
yNode *tree1,*tree2,*tree3,*tree4;
void init(int R,int C,int sr,int sc,int M,char *S) {
    int i;
    r = R,c = C;
    tree1 = new yNode;
    tree2 = new yNode;
    tree3 = new yNode;
    tree4 = new yNode;
    sr--,sc--;
    lx = rx = sc,ly = ry = sr;
    p1.pb(mp(sr+1,sc+1));
    p2.pb(mp(sr+1,sc+1)),p2.pb(mp(sr,sc+1));
    p3.pb(mp(sr+1,sc+1)),p3.pb(mp(sr+1,sc));
    p4.pb(mp(sr+1,sc+1)),p4.pb(mp(sr,sc+1)),p4.pb(mp(sr+1,sc)),p4.pb(mp(sr,sc));
    for (i = 0; i < M; i++) {
        if (S[i] == 'N') sr--;
        else if (S[i] == 'S') sr++;
        else if (S[i] == 'W') sc--;
        else sc++;
        lx = min(lx,sc),rx = max(rx,sc);
        ly = min(lx,sr),ry = max(ry,sr);
        p1.pb(mp(sr+1,sc+1));
        p2.pb(mp(sr+1,sc+1)),p2.pb(mp(sr,sc+1));
        p3.pb(mp(sr+1,sc+1)),p3.pb(mp(sr+1,sc));
        p4.pb(mp(sr+1,sc+1)),p4.pb(mp(sr,sc+1)),p4.pb(mp(sr+1,sc)),p4.pb(mp(sr,sc));
    }
    sort(p1.begin(),p1.end());
    p1.resize(unique(p1.begin(),p1.end())-p1.begin());
    sort(p2.begin(),p2.end());
    p2.resize(unique(p2.begin(),p2.end())-p2.begin());
    sort(p3.begin(),p3.end());
    p3.resize(unique(p3.begin(),p3.end())-p3.begin());
    sort(p4.begin(),p4.end());
    p4.resize(unique(p4.begin(),p4.end())-p4.begin());
    for (i = 0; i < p1.size(); i++) tree1->update(0,r,p1[i].first,p1[i].second);
    for (i = 0; i < p2.size(); i++) tree2->update(0,r,p2[i].first,p2[i].second);
    for (i = 0; i < p3.size(); i++) tree3->update(0,r,p3[i].first,p3[i].second);
    for (i = 0; i < p4.size(); i++) tree4->update(0,r,p4[i].first,p4[i].second);
}

int colour(int ar,int ac,int br,int bc) {
    ar--,ac--,br--,bc--;
    LLI ans = 0;
    ans += (LLI) (br-ar+1)*(bc-ac+1)-tree1->query(0,r,ar+1,br+1,ac+1,bc+1);
    ans -= (LLI) (br-ar)*(bc-ac+1)-tree2->query(0,r,ar+1,br,ac+1,bc+1);
    ans -= (LLI) (br-ar+1)*(bc-ac)-tree3->query(0,r,ar+1,br+1,ac+1,bc);
    ans += (LLI) (br-ar)*(bc-ac)-tree4->query(0,r,ar+1,br,ac+1,bc);
    if ((ar < ly) && (br > ry) && (ac < lx) && (bc > rx)) ans++;
    return ans;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:157:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p1.size(); i++) tree1->update(0,r,p1[i].first,p1[i].second);
                 ~~^~~~~~~~~~~
rainbow.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p2.size(); i++) tree2->update(0,r,p2[i].first,p2[i].second);
                 ~~^~~~~~~~~~~
rainbow.cpp:159:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p3.size(); i++) tree3->update(0,r,p3[i].first,p3[i].second);
                 ~~^~~~~~~~~~~
rainbow.cpp:160:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p4.size(); i++) tree4->update(0,r,p4[i].first,p4[i].second);
                 ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 9 ms 1412 KB Output is correct
3 Correct 6 ms 1412 KB Output is correct
4 Correct 6 ms 1412 KB Output is correct
5 Correct 10 ms 1660 KB Output is correct
6 Correct 2 ms 1660 KB Output is correct
7 Correct 2 ms 1660 KB Output is correct
8 Correct 2 ms 1660 KB Output is correct
9 Correct 2 ms 1660 KB Output is correct
10 Correct 2 ms 1660 KB Output is correct
11 Correct 6 ms 1660 KB Output is correct
12 Correct 8 ms 1660 KB Output is correct
13 Correct 10 ms 2176 KB Output is correct
14 Correct 13 ms 2468 KB Output is correct
15 Correct 2 ms 2468 KB Output is correct
16 Correct 2 ms 2468 KB Output is correct
17 Correct 2 ms 2468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2468 KB Output is correct
2 Correct 2 ms 2468 KB Output is correct
3 Correct 411 ms 56860 KB Output is correct
4 Correct 641 ms 96756 KB Output is correct
5 Correct 840 ms 98724 KB Output is correct
6 Correct 567 ms 98724 KB Output is correct
7 Correct 616 ms 98724 KB Output is correct
8 Correct 147 ms 98724 KB Output is correct
9 Correct 680 ms 103176 KB Output is correct
10 Correct 705 ms 103176 KB Output is correct
11 Correct 757 ms 103176 KB Output is correct
12 Correct 509 ms 103176 KB Output is correct
13 Correct 511 ms 103176 KB Output is correct
14 Correct 479 ms 103176 KB Output is correct
15 Correct 405 ms 103176 KB Output is correct
16 Correct 447 ms 103176 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2468 KB Output is correct
2 Correct 1737 ms 496060 KB Output is correct
3 Correct 1518 ms 521396 KB Output is correct
4 Correct 1929 ms 529256 KB Output is correct
5 Correct 1248 ms 529256 KB Output is correct
6 Correct 293 ms 529256 KB Output is correct
7 Correct 500 ms 529256 KB Output is correct
8 Correct 432 ms 529256 KB Output is correct
9 Correct 656 ms 529256 KB Output is correct
10 Correct 203 ms 529256 KB Output is correct
11 Correct 752 ms 529256 KB Output is correct
12 Correct 2355 ms 529256 KB Output is correct
13 Correct 1554 ms 529256 KB Output is correct
14 Correct 1876 ms 530088 KB Output is correct
15 Correct 1311 ms 530088 KB Output is correct
16 Correct 287 ms 530088 KB Output is correct
17 Correct 490 ms 530088 KB Output is correct
18 Correct 1205 ms 530088 KB Output is correct
19 Correct 1658 ms 530088 KB Output is correct
20 Correct 1624 ms 530088 KB Output is correct
21 Correct 546 ms 530088 KB Output is correct
22 Correct 507 ms 530088 KB Output is correct
23 Correct 219 ms 530088 KB Output is correct
24 Correct 1250 ms 530088 KB Output is correct
25 Correct 1899 ms 530088 KB Output is correct
26 Correct 1673 ms 530088 KB Output is correct
27 Correct 1944 ms 531432 KB Output is correct
28 Correct 1240 ms 531432 KB Output is correct
29 Correct 349 ms 531432 KB Output is correct
30 Correct 624 ms 531432 KB Output is correct
31 Correct 1175 ms 531432 KB Output is correct
32 Correct 1764 ms 531432 KB Output is correct
33 Correct 1680 ms 531432 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 9 ms 1412 KB Output is correct
3 Correct 6 ms 1412 KB Output is correct
4 Correct 6 ms 1412 KB Output is correct
5 Correct 10 ms 1660 KB Output is correct
6 Correct 2 ms 1660 KB Output is correct
7 Correct 2 ms 1660 KB Output is correct
8 Correct 2 ms 1660 KB Output is correct
9 Correct 2 ms 1660 KB Output is correct
10 Correct 2 ms 1660 KB Output is correct
11 Correct 6 ms 1660 KB Output is correct
12 Correct 8 ms 1660 KB Output is correct
13 Correct 10 ms 2176 KB Output is correct
14 Correct 13 ms 2468 KB Output is correct
15 Correct 2 ms 2468 KB Output is correct
16 Correct 2 ms 2468 KB Output is correct
17 Correct 2 ms 2468 KB Output is correct
18 Execution timed out 3070 ms 531432 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 9 ms 1412 KB Output is correct
3 Correct 6 ms 1412 KB Output is correct
4 Correct 6 ms 1412 KB Output is correct
5 Correct 10 ms 1660 KB Output is correct
6 Correct 2 ms 1660 KB Output is correct
7 Correct 2 ms 1660 KB Output is correct
8 Correct 2 ms 1660 KB Output is correct
9 Correct 2 ms 1660 KB Output is correct
10 Correct 2 ms 1660 KB Output is correct
11 Correct 6 ms 1660 KB Output is correct
12 Correct 8 ms 1660 KB Output is correct
13 Correct 10 ms 2176 KB Output is correct
14 Correct 13 ms 2468 KB Output is correct
15 Correct 2 ms 2468 KB Output is correct
16 Correct 2 ms 2468 KB Output is correct
17 Correct 2 ms 2468 KB Output is correct
18 Execution timed out 3070 ms 531432 KB Time limit exceeded
19 Halted 0 ms 0 KB -