oj.uz

Submission #250892

# Submission time Handle Problem Language Result Execution time Memory
250892 2020-07-19T10:59:43 Z receed Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 473 ms 70776 KB 
#include "rainbow.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <string>
#include <set>
#include <map>
#include <random>
#include <bitset>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;

const int N = 1 << 18, M = N * 40;
int tr[M], lv[M], rv[M], sz = 1, rt[N];
set<pair<int, int>> ss, ts;
map<int, vector<int>> mh, mv;
int lx, rx, ly, ry;

int add(int v, int p, int x, int l=0, int r=N) {
    int cv = sz++;
    tr[cv] = tr[v] + x;
    if (r - l == 1)
        lv[cv] = rv[cv] = -1;
    else if (p < (l + r) / 2) {
        lv[cv] = add(lv[v], p, x, l, (l + r) / 2);
        rv[cv] = rv[v];
    }
    else {
        lv[cv] = lv[v];
        rv[cv] = add(rv[v], p, x, (l + r) / 2, r);
    }
    return cv;
}

int sum(int v, int cl, int cr, int l=0, int r=N) {
    if (v == -1 || cr <= l || r <= cl)
        return 0;
    if (cl <= l && r <= cr)
        return tr[v];
    return sum(lv[v], cl, cr, l, (l + r) / 2) + sum(rv[v], cl, cr, (l + r) / 2, r);
}

void init(int r, int c, int sr, int sc, int m, char *s) {
    lx = rx = sr;
    ly = ry = sc;
    ss.insert({sr, sc});
    rep(i, m) {
        if (s[i] == 'N') sr--;
        else if (s[i] == 'S') sr++;
        else if (s[i] == 'W') sc--;
        else sc++;
        lx = min(lx, sr);
        rx = max(rx, sr);
        ly = min(ly, sc);
        ry = max(ry, sc);
        ss.insert({sr, sc});
    }
    for (auto &p : ss) {
        // cout << p.first << ' ' << p.second << '\n';
        ts.insert(p);
        if (p.first > 1) {
            ts.insert({p.first - 1, p.second});
            if (p.second > 1)
                ts.insert({p.first - 1, p.second - 1});
        }
        if (p.second > 1)
            ts.insert({p.first, p.second - 1});
    }
    int crt = 0, ls = 0;
    for (auto &p : ts) {
        while (ls < p.first)
            rt[ls++] = crt;
        int val = -1;
        if (ss.count(p)) {
            val += 1;
            if (!ss.count({p.first, p.second + 1}))
                mh[p.first].push_back(p.second);
            if (!ss.count({p.first + 1, p.second}))
                mv[p.second].push_back(p.first);
        }
        else {
            if (ss.count({p.first, p.second + 1}))
                val++;
            if (ss.count({p.first + 1, p.second}))
                val++;
        }
        crt = add(crt, p.second, val);
    }
    for (auto &p : mh)
        sort(all(p.second));
    for (auto &p : mv)
        sort(all(p.second));
}

int colour(int ar, int ac, int br, int bc) {
    ll ans = 1 + sum(rt[br - 1], ac, bc) - sum(rt[ar - 1], ac, bc);
    // cout << ans << '\n';
    if (mh.count(br))
        ans += lower_bound(all(mh[br]), bc) - lower_bound(all(mh[br]), ac);
    if (mv.count(bc))
        ans += lower_bound(all(mv[bc]), br) - lower_bound(all(mv[bc]), ar);
    if (ss.count({br, ac}))
        ans--;
    if (ss.count({ar, bc}))
        ans--;
    if (ss.count({br, bc}))
        ans++;
    if (ar < lx && rx < br && ac < ly && ry < bc)
        ans++;
    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Incorrect 2 ms 512 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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 348 ms 38392 KB Output is correct
4 Correct 457 ms 59996 KB Output is correct
5 Correct 452 ms 57720 KB Output is correct
6 Correct 355 ms 39928 KB Output is correct
7 Correct 437 ms 40280 KB Output is correct
8 Correct 149 ms 4088 KB Output is correct
9 Correct 473 ms 59384 KB Output is correct
10 Correct 472 ms 57464 KB Output is correct
11 Correct 388 ms 39912 KB Output is correct
12 Correct 318 ms 59000 KB Output is correct
13 Correct 312 ms 59640 KB Output is correct
14 Correct 315 ms 57596 KB Output is correct
15 Correct 246 ms 39800 KB Output is correct
16 Correct 347 ms 40184 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 247 ms 70648 KB Output is correct
3 Correct 241 ms 70776 KB Output is correct
4 Correct 234 ms 70392 KB Output is correct
5 Correct 173 ms 53112 KB Output is correct
6 Correct 41 ms 10880 KB Output is correct
7 Incorrect 73 ms 19960 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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