oj.uz

Submission #218325

# Submission time Handle Problem Language Result Execution time Memory
218325 2020-04-02T01:45:20 Z anonymous Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 676 ms 161528 KB 
#include "rainbow.h"
#include <set>
#include <utility>
#include <iostream>
#define MAXN 100005
using namespace std;

class PersistentSegtree {
    int ST[MAXN*40][3], R[MAXN*2], X[MAXN*2];
    int V=1, P=1;
    int upd(int ind, int l, int r, int cur) {
        if (l > ind || ind > r) {return(cur);}
        if (l == r) {
            ST[V][0] = ST[cur][0] + 1, V++;
            return(V-1);
        } else {
            int mid = (l + r) >> 1, at = V;
            V++;
            ST[at][1] = upd(ind, l, mid, ST[cur][1]);
            ST[at][2] = upd(ind, mid+1, r, ST[cur][2]);
            ST[at][0] = ST[ST[at][1]][0] + ST[ST[at][2]][0];
            return(at);
        }
    }
    int ask(int lo, int hi, int l, int r, int cur) {
        if (l > hi || r < lo || cur == 0) {return(0);}
        else if (lo <= l && hi >= r) {return(ST[cur][0]);}
        else {
            int mid = (l + r) >> 1;
            return(ask(lo, hi, l, mid, ST[cur][1])+
                   ask(lo, hi, mid+1, r, ST[cur][2]));
        }
    }
public:
    void put(int x, int y) {
        X[P] = x;
        R[P] = upd(y, 1, MAXN, R[P-1]);
        P++;
    }
    int lb(int x) {
        int lo = 0, hi = P;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (X[mid] > x) {hi = mid;}
            else {lo = mid;}
        }
        return(lo);
    }
    int ask(int xlo, int ylo, int xhi, int yhi) {
        if (xlo > xhi || ylo > yhi) {return(0);}
        int ql = lb(xlo-1), qr = lb(xhi);
        return(ask(ylo, yhi, 1, MAXN, R[qr])-
               ask(ylo, yhi, 1, MAXN, R[ql]));
    }
} rT, vT, hT, VT;
int R,C;
set<pair<int,int> > rS, vS, hS, VS;

void init(int r, int c, int sr, int sc, int M, char *S) {
    R = r, C = c;
    int x = sr, y = sc; //cur
    for (int i=0; i<=M; i++) {
        //printf("At %d %d\n",x,y);
        rS.insert({x, y}); //river
        vS.insert({x,y}); //lines
        vS.insert({x,y+1});
        hS.insert({x,y});
        hS.insert({x+1,y});
        VS.insert({x,y}); //vertex
        VS.insert({x+1,y});
        VS.insert({x,y+1});
        VS.insert({x+1,y+1});
        if (i == M) {break;}
        switch(S[i]) {
            case 'N':
                x--;
                break;
            case 'S':
                x++;
                break;
            case 'W':
                y--;
                break;
            case 'E':
                y++;
                break;
        }
    }
    for (auto p: rS) {
        rT.put(p.first,p.second);
    }
    for (auto p: vS) {
        vT.put(p.first,p.second);
    }
    for (auto p: hS) {
        hT.put(p.first,p.second);
    }
    for (auto p: VS) {
        VT.put(p.first,p.second);
    }
}

int colour(int ar, int ac, int br, int bc) {
    int V = VT.ask(ar+1, ac+1, br, bc) + 2*(br+bc-ar-ac) + 4;
    int Fr = rT.ask(ar, ac, br, bc);
    int E = hT.ask(ar+1, ac, br, bc) + vT.ask(ar, ac+1, br, bc) + 2*(br+bc-ar-ac) + 4;
    int ans = E - V - Fr + 1;
    return(ans);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 11 ms 1792 KB Output is correct
3 Incorrect 7 ms 640 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 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 412 ms 97912 KB Output is correct
4 Correct 631 ms 161476 KB Output is correct
5 Correct 644 ms 160280 KB Output is correct
6 Correct 537 ms 124536 KB Output is correct
7 Correct 640 ms 122232 KB Output is correct
8 Correct 92 ms 4192 KB Output is correct
9 Correct 657 ms 161528 KB Output is correct
10 Correct 676 ms 160248 KB Output is correct
11 Correct 570 ms 124280 KB Output is correct
12 Correct 435 ms 150520 KB Output is correct
13 Correct 438 ms 161444 KB Output is correct
14 Correct 465 ms 160236 KB Output is correct
15 Correct 432 ms 124408 KB Output is correct
16 Correct 451 ms 115320 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 329 ms 95992 KB Output is correct
3 Correct 357 ms 160220 KB Output is correct
4 Correct 369 ms 158328 KB Output is correct
5 Correct 280 ms 118624 KB Output is correct
6 Correct 91 ms 6648 KB Output is correct
7 Incorrect 216 ms 59512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 11 ms 1792 KB Output is correct
3 Incorrect 7 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 11 ms 1792 KB Output is correct
3 Incorrect 7 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -