oj.uz

Submission #59636

# Submission time Handle Problem Language Result Execution time Memory
59636 2018-07-22T19:36:59 Z duality Land of the Rainbow Gold (APIO17_rainbow) C++11
23 / 100
 2092 ms 1049600 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;
int **pre1,**pre2,**pre3,**pre4;
void init(int R,int C,int sr,int sc,int M,char *S) {
    int i,j;
    r = R,c = C;
    pre1 = new int*[R+1];
    pre2 = new int*[R+1];
    pre3 = new int*[R+1];
    pre4 = new int*[R+1];
    for (i = 0; i <= R; i++) {
        pre1[i] = new int[C+1];
        pre2[i] = new int[C+1];
        pre3[i] = new int[C+1];
        pre4[i] = new int[C+1];
        for (j = 0; j <= C; j++) pre1[i][j] = pre2[i][j] = pre3[i][j] = pre4[i][j] = 0;
    }
    for (i = 1; i <= R; i++) {
        for (j = 1; j <= C; j++) pre1[i][j] = pre2[i][j] = pre3[i][j] = pre4[i][j] = 1;
    }
    sr--,sc--;
    lx = rx = sc,ly = ry = sr;
    pre1[sr+1][sc+1] = 0;
    pre2[sr+1][sc+1] = pre2[sr][sc+1] = 0;
    pre3[sr+1][sc+1] = pre3[sr+1][sc] = 0;
    pre4[sr+1][sc+1] = pre4[sr][sc+1] = pre4[sr+1][sc] = pre4[sr][sc] = 0;
    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);
        pre1[sr+1][sc+1] = 0;
        pre2[sr+1][sc+1] = pre2[sr][sc+1] = 0;
        pre3[sr+1][sc+1] = pre3[sr+1][sc] = 0;
        pre4[sr+1][sc+1] = pre4[sr][sc+1] = pre4[sr+1][sc] = pre4[sr][sc] = 0;
    }
    for (i = 1; i <= R; i++) {
        for (j = 1; j <= C; j++) {
            pre1[i][j] += pre1[i-1][j]+pre1[i][j-1]-pre1[i-1][j-1];
            pre2[i][j] += pre2[i-1][j]+pre2[i][j-1]-pre2[i-1][j-1];
            pre3[i][j] += pre3[i-1][j]+pre3[i][j-1]-pre3[i-1][j-1];
            pre4[i][j] += pre4[i-1][j]+pre4[i][j-1]-pre4[i-1][j-1];
        }
    }
}

int colour(int ar,int ac,int br,int bc) {
    ar--,ac--,br--,bc--;
    int ans = 0;
    ans += pre1[br+1][bc+1]-pre1[ar][bc+1]-pre1[br+1][ac]+pre1[ar][ac];
    ans -= pre2[br][bc+1]-pre2[ar][bc+1]-pre2[br][ac]+pre2[ar][ac];
    ans -= pre3[br+1][bc]-pre3[ar][bc]-pre3[br+1][ac]+pre3[ar][ac];
    ans += pre4[br][bc]-pre4[ar][bc]-pre4[br][ac]+pre4[ar][ac];
    if ((ar < ly) && (br > ry) && (ac < lx) && (bc > rx)) ans++;
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 4 ms 500 KB Output is correct
3 Correct 5 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 4 ms 684 KB Output is correct
6 Correct 3 ms 684 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 740 KB Output is correct
11 Correct 3 ms 880 KB Output is correct
12 Correct 3 ms 880 KB Output is correct
13 Correct 3 ms 880 KB Output is correct
14 Correct 5 ms 880 KB Output is correct
15 Correct 3 ms 880 KB Output is correct
16 Correct 3 ms 880 KB Output is correct
17 Correct 3 ms 880 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 880 KB Output is correct
2 Correct 3 ms 880 KB Output is correct
3 Correct 156 ms 13832 KB Output is correct
4 Correct 125 ms 16744 KB Output is correct
5 Correct 148 ms 19744 KB Output is correct
6 Correct 142 ms 22548 KB Output is correct
7 Correct 138 ms 22876 KB Output is correct
8 Correct 165 ms 23080 KB Output is correct
9 Correct 108 ms 23080 KB Output is correct
10 Correct 105 ms 23080 KB Output is correct
11 Correct 116 ms 23080 KB Output is correct
12 Correct 95 ms 23080 KB Output is correct
13 Correct 92 ms 23080 KB Output is correct
14 Correct 84 ms 23080 KB Output is correct
15 Correct 129 ms 23080 KB Output is correct
16 Correct 128 ms 23080 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 880 KB Output is correct
2 Runtime error 2092 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 4 ms 500 KB Output is correct
3 Correct 5 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 4 ms 684 KB Output is correct
6 Correct 3 ms 684 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 740 KB Output is correct
11 Correct 3 ms 880 KB Output is correct
12 Correct 3 ms 880 KB Output is correct
13 Correct 3 ms 880 KB Output is correct
14 Correct 5 ms 880 KB Output is correct
15 Correct 3 ms 880 KB Output is correct
16 Correct 3 ms 880 KB Output is correct
17 Correct 3 ms 880 KB Output is correct
18 Runtime error 145 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 248 KB Output is correct
2 Correct 4 ms 500 KB Output is correct
3 Correct 5 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 4 ms 684 KB Output is correct
6 Correct 3 ms 684 KB Output is correct
7 Correct 2 ms 684 KB Output is correct
8 Correct 3 ms 684 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 3 ms 740 KB Output is correct
11 Correct 3 ms 880 KB Output is correct
12 Correct 3 ms 880 KB Output is correct
13 Correct 3 ms 880 KB Output is correct
14 Correct 5 ms 880 KB Output is correct
15 Correct 3 ms 880 KB Output is correct
16 Correct 3 ms 880 KB Output is correct
17 Correct 3 ms 880 KB Output is correct
18 Runtime error 145 ms 1049600 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
19 Halted 0 ms 0 KB -