oj.uz

Submission #218324

# Submission time Handle Problem Language Result Execution time Memory
218324 2020-04-02T01:39:44 Z anonymous Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 11 ms 1920 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++) {
        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;
    if (ar == 1 && ac == 1 && br == R && bc == C) {ans+=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 10 ms 1664 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 8 ms 768 KB Output is correct
5 Correct 11 ms 1920 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 640 KB Output is correct
2 Correct 10 ms 1664 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 8 ms 768 KB Output is correct
5 Correct 11 ms 1920 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 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 10 ms 1664 KB Output is correct
3 Correct 7 ms 768 KB Output is correct
4 Correct 8 ms 768 KB Output is correct
5 Correct 11 ms 1920 KB Output is correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -