oj.uz

Submission #1064512

# Submission time Handle Problem Language Result Execution time Memory
1064512 2024-08-18T13:44:32 Z abczz Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 433 ms 263520 KB 
#include "rainbow.h"
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <map>
#define ll long long

using namespace std;

vector <array<ll, 2>> V;
map <array<ll, 2>, ll> mp, vert, edger, edgec;
string T = "NESW";
vector <ll> X[200001], VR[200001], ER[200001], EC[200001], G[200001];
ll x, y, r, c, nx, ny, tot, e, v, f, dj[4][2] = {0, 0, 0, 1, 1, 0, 1, 1}, dr[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

struct SegTree2D{
    vector <ll> st[800004];
    void build(ll id, ll l, ll r) {
        if (l == r) {
            st[id] = X[l];
            return;
        }
        ll mid = (l+r)/2;
        build(id*2, l, mid);
        build(id*2+1, mid+1, r);
        int i = 0, j = 0;
        while (i < st[id*2].size() && j < st[id*2+1].size()) {
            if (st[id*2][i] <= st[id*2+1][j]) st[id].push_back(st[id*2][i++]);
            else st[id].push_back(st[id*2+1][j++]);
        }
        while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
        while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
    }
    ll query(ll id, ll l, ll r, ll xl, ll xr, ll yl, ll yr) {
        if (xr < l || r < xl || xl > xr || yl > yr) return 0;
        else if (xl <= l && r <= xr) {
            auto it = lower_bound(st[id].begin(), st[id].end(), yl);
            auto it2 = lower_bound(st[id].begin(), st[id].end(), yr+1);
            return (it2-st[id].begin())-(it-st[id].begin());
        }
        ll mid = (l+r)/2;
        return query(id*2, l, mid, xl, xr, yl, yr) + query(id*2+1, mid+1, r, xl, xr, yl, yr);
    }
}STV, STER, STEC, ST;

void init(int R, int C, int sr, int sc, int M, char *S) {
    r = R, c = C;
    mp.clear();
    V.clear();
    V.push_back({sr, sc});
    x = sr, y = sc;
    for (int j=0; j<M; ++j) {
        auto u = S[j];
        for (int i=0; i<4; ++i) {
            if (u == T[i]) {
                nx = x + dr[i][0], ny = y + dr[i][1];
                x = nx, y = ny;
                V.push_back({x, y});
                break;
            }
        }
    }
    for (int i=0; i<V.size(); ++i) {
        --V[i][0], --V[i][1];
        x = V[i][0], y = V[i][1];
        if (!mp.count({x, y})) ++mp[{x, y}];
        for (int j=0; j<4; ++j) {
            nx = x + dj[j][0], ny = y + dj[j][1];
            ++vert[{nx, ny}];
        }
        ++edger[{x, y}];
        ++edger[{x+1, y}];
        ++edgec[{x, y}];
        ++edgec[{x, y+1}];
    }
    for (auto it = edger.begin(); it != edger.end();) {
        auto nx = next(it);
        auto [x, y] = it->first;
        ER[x].push_back(y);
        it = nx;
    }
    for (auto it = edgec.begin(); it != edgec.end();) {
        auto nx = next(it);
        auto [x, y] = it->first;
        EC[y].push_back(x);
        it = nx;
    }
    for (auto it = vert.begin(); it != vert.end();) {
        auto nxt = next(it);
        auto [x, y] = it->first;
        VR[x].push_back(y);
        it = nxt;
    }
    for (auto it = mp.begin(); it != mp.end();) {
        auto nxt = next(it);
        auto [x, y] = it->first;
        G[x].push_back(y);
        it = nxt;
    }
    for (int i=0; i<=R; ++i) {
        sort(VR[i].begin(), VR[i].end());
        sort(ER[i].begin(), ER[i].end());
    }
    for (int i=0; i<=C; ++i) {
        sort(EC[i].begin(), EC[i].end());
    }
    for (int i=0; i<=R; ++i) swap(X[i], VR[i]);
    STV.build(1, 0, R);
    for (int i=0; i<=R; ++i) swap(X[i], ER[i]);
    STER.build(1, 0, R);
    for (int i=0; i<=C; ++i) swap(X[i], EC[i]);
    STEC.build(1, 0, C);
    for (int i=0; i<=R; ++i) swap(X[i], G[i]);
    ST.build(1, 0, R);
}

int colour(int ar, int ac, int br, int bc) {
    --ar, --ac;
    e = STER.query(1, 0, r, ar+1, br-1, ac, bc-1) + STEC.query(1, 0, c, ac+1, bc-1, ar, br-1) + (br-ar+bc-ac) * 2;
    v = STV.query(1, 0, r, ar+1, br-1, ac+1, bc-1) + (br-ar+bc-ac) * 2;
    f = e-v+1;
    return f-ST.query(1, 0, r, ar, br-1, ac, bc-1);
}

Compilation message

rainbow.cpp: In member function 'void SegTree2D::build(long long int, long long int, long long int)':
rainbow.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |                ~~^~~~~~~~~~~~~~~~~
rainbow.cpp:28:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |                                       ~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
      |                ~~^~~~~~~~~~~~~~~~~
rainbow.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
      |                ~~^~~~~~~~~~~~~~~~~~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i=0; i<V.size(); ++i) {
      |                   ~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 99156 KB Output is correct
2 Correct 41 ms 99640 KB Output is correct
3 Incorrect 42 ms 99164 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 40 ms 98900 KB Output is correct
2 Correct 39 ms 98908 KB Output is correct
3 Correct 304 ms 149824 KB Output is correct
4 Correct 415 ms 182196 KB Output is correct
5 Correct 433 ms 181184 KB Output is correct
6 Correct 363 ms 164788 KB Output is correct
7 Correct 389 ms 164288 KB Output is correct
8 Correct 139 ms 104640 KB Output is correct
9 Correct 412 ms 182196 KB Output is correct
10 Correct 419 ms 181168 KB Output is correct
11 Correct 379 ms 164800 KB Output is correct
12 Correct 341 ms 176576 KB Output is correct
13 Correct 329 ms 182200 KB Output is correct
14 Correct 354 ms 180936 KB Output is correct
15 Correct 302 ms 164780 KB Output is correct
16 Correct 331 ms 159788 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 98972 KB Output is correct
2 Correct 344 ms 240576 KB Output is correct
3 Correct 346 ms 259008 KB Output is correct
4 Correct 334 ms 263520 KB Output is correct
5 Correct 277 ms 215428 KB Output is correct
6 Correct 131 ms 127804 KB Output is correct
7 Incorrect 189 ms 154048 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 99156 KB Output is correct
2 Correct 41 ms 99640 KB Output is correct
3 Incorrect 42 ms 99164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 99156 KB Output is correct
2 Correct 41 ms 99640 KB Output is correct
3 Incorrect 42 ms 99164 KB Output isn't correct
4 Halted 0 ms 0 KB -