oj.uz

Submission #384171

# Submission time Handle Problem Language Result Execution time Memory
384171 2021-03-31T15:59:49 Z BartolM Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 684 ms 160548 KB 
#define DEBUG 0
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int OFF=(1<<18);

int uk=1;
int lef[150*N], rig[150*N], val[150*N];
vector <int> v_br[N], v_v[N], v_ok[N], v_vod[N];

int novi(int x, int l, int r) {
    lef[uk]=l; rig[uk]=r;
    val[uk]=x;
    return uk++;
}

int upd(int ind, int pos, int lo, int hi) {
    if (ind>=hi || ind<lo) return pos;
    if (lo==hi-1) return novi(1+val[pos], 0, 0);
    int mid=(lo+hi)/2;
    return novi(1+val[pos], upd(ind, lef[pos], lo, mid), upd(ind, rig[pos], mid, hi));
}

int que(int a, int b, int pos, int lo, int hi) {
    if (!pos) return 0;
    if (lo>=b || hi<=a) return 0;
    if (lo>=a && hi<=b) return val[pos];
    int mid=(lo+hi)/2;
    return que(a, b, lef[pos], lo, mid)+que(a, b, rig[pos], mid, hi);
}

struct Tour{
    int T[N];
    Tour() {
        memset(T, 0, sizeof T);
    }
    int& operator [] (int x) {
        return T[x];
    }
    void update(int r, int c) {
        if (T[r]==0) T[r]=T[r-1];
        T[r]=upd(c, T[r], 0, OFF);
    }
    int query(int r1, int c1, int r2, int c2) {
        return que(c1, c2+1, T[r2], 0, OFF)-que(c1, c2+1, T[r1-1], 0, OFF);
    }
};

int mxr, mnr, mxc, mnc;

void dodaj(int r, int c) {
    v_br[r].pb(c);

    v_v[r].pb(c); v_v[r].pb(c+1);
    v_v[r+1].pb(c); v_v[r+1].pb(c+1);

    v_ok[r].pb(c); v_ok[r].pb(c+1);
    v_vod[r].pb(c); v_vod[r+1].pb(c);
    mxr=max(mxr, r); mxc=max(mxc, c);
    mnr=min(mnr, r); mnc=min(mnc, c);
}

void sazmi(vector <int> &v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
}

Tour Tvod, Tok, Tv, Tbr;

void init(int R, int C, int sr, int sc, int M, char *S) {
    mxr=mnr=sr; mxc=mnc=sc;
    dodaj(sr, sc);
    for (int i=0; i<M; ++i) {
        if (S[i]=='N') sr--;
        if (S[i]=='S') sr++;
        if (S[i]=='W') sc--;
        if (S[i]=='E') sc++;
        dodaj(sr, sc);
    }
    for (int i=1; i<=R; ++i) {
        sazmi(v_br[i]); sazmi(v_v[i]); sazmi(v_ok[i]); sazmi(v_vod[i]);
        for (int x:v_br[i]) Tbr.update(i, x);
        for (int x:v_v[i]) Tv.update(i, x);
        for (int x:v_ok[i]) Tok.update(i, x);
        for (int x:v_vod[i]) Tvod.update(i, x);
    }
}

int colour(int r1, int c1, int r2, int c2) {
    int red=r2-r1+1, col=c2-c1+1;

    int v=Tv.query(r1+1, c1+1, r2, c2)+2*(red+col);
    int e=Tok.query(r1, c1+1, r2, c2)+Tvod.query(r1+1, c1, r2, c2)+2*(red+col);
    int comp=1;
    if (r1<mnr && r2>mxr && c1<mnc && c2>mxc) ++comp;
    int f=1-v+e+comp;
    int br=Tbr.query(r1, c1, r2, c2);
#if DEBUG
    printf("v: %d, e: %d, comp: %d\nf: %d, br: %d\n", v, e, comp, f, br);
#endif // DEBUG
    return f-br-1;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22508 KB Output is correct
2 Correct 18 ms 23404 KB Output is correct
3 Incorrect 16 ms 22636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22252 KB Output is correct
2 Correct 14 ms 22252 KB Output is correct
3 Correct 412 ms 93924 KB Output is correct
4 Correct 656 ms 141776 KB Output is correct
5 Correct 655 ms 140116 KB Output is correct
6 Correct 455 ms 112852 KB Output is correct
7 Correct 644 ms 114276 KB Output is correct
8 Correct 106 ms 30552 KB Output is correct
9 Correct 684 ms 142092 KB Output is correct
10 Correct 675 ms 140168 KB Output is correct
11 Correct 495 ms 112464 KB Output is correct
12 Correct 287 ms 129620 KB Output is correct
13 Correct 365 ms 141264 KB Output is correct
14 Correct 396 ms 139516 KB Output is correct
15 Correct 354 ms 112848 KB Output is correct
16 Correct 467 ms 113612 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22252 KB Output is correct
2 Incorrect 269 ms 160548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22508 KB Output is correct
2 Correct 18 ms 23404 KB Output is correct
3 Incorrect 16 ms 22636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22508 KB Output is correct
2 Correct 18 ms 23404 KB Output is correct
3 Incorrect 16 ms 22636 KB Output isn't correct
4 Halted 0 ms 0 KB -