oj.uz

Submission #557068

# Submission time Handle Problem Language Result Execution time Memory
557068 2022-05-04T17:06:52 Z nutella Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 287 ms 89464 KB 
#include "rainbow.h"

//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18

template<typename T>
void make_uniq(vector<T> &v) {
    sort(all(v));
    v.resize(unique(all(v)) - begin(v));
}

struct Fenwick {
    vector<vector<ll>> t;
    vector<vector<int>> yy;
    int n;


    Fenwick() = default;

    void init(int a) {
        n = a;
        yy.resize(n);
        t.resize(n);
    }

    void fake_add(int x, int y) {
        for (int i = x; i < n; i |= (i + 1))
            yy[i].pb(y);
    }

    void build() {
        for (int i = 0; i < n; ++i) {
            make_uniq(yy[i]);
            t[i].resize(sz(yy[i]) + 2);
        }
    }

    void add(int x, int y) {
        for (int i = x; i < n; i |= (i + 1))
            for (int j = upper_bound(all(yy[i]), y) - begin(yy[i]) - 1; j < sz(yy[i]); j |= (j + 1))
                ++t[i][j];
    }

    ll get(int x, int y) {
        ll ans = 0;
        for (int i = x; i > -1; i = ((i + 1) & i) - 1)
            for (int j = upper_bound(all(yy[i]), y) - begin(yy[i]) - 1; j > -1; j = ((j + 1) & j) - 1)
                ans += t[i][j];
        return ans;
    }

    ll get(int x1, int y1, int x2, int y2) {
        return get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
    }

};
const int dx[4] = {0, 0, 1, -1};

const int dy[4] = {1, -1, 0, 0};
int n, m;
vector<pair<int, int>> yy;

Fenwick fx, fy, fv, cv;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    --sr, --sc;
    fx.init(n), fy.init(n), fv.init(n), cv.init(n);
    yy = {{sr, sc}};
    for (int i = 0; i < M; ++i) {
        if (S[i] == 'N') --sr;
        else if (S[i] == 'S') ++sr;
        else if (S[i] == 'W') --sc;
        else ++sc;
        yy.emplace_back(sr, sc);
    }
    make_uniq(yy);

    auto here = [](int x, int y) -> bool {
        auto it = lower_bound(all(yy), mp(x, y));
        if (it == end(yy)) return false;
        return (*it) == mp(x, y);
    };
    vector<pii > pv, px, py, cvv;
    for (auto [x, y]: yy) {;
        pv.emplace_back(x, y);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (here(nx, ny)) {
                if (nx == x) {
                    px.emplace_back(x, min(ny, y));
                } else {
                    py.emplace_back(min(nx, x), y);
                }
            }
        }
        if (here(x + 1, y) && here(x, y + 1) && here(x + 1, y + 1)) {
            cvv.emplace_back(x, y);
        }
    }

    make_uniq(pv), make_uniq(px), make_uniq(py), make_uniq(cvv);

    for (auto [x, y] : pv)
        fv.fake_add(x, y);
    for (auto [x, y] : px)
        fx.fake_add(x, y);
    for (auto [x, y] : py)
        fy.fake_add(x, y);
    for (auto [x, y] : cvv)
        cv.fake_add(x, y);

    fv.build(), fx.build(), fy.build(), cv.build();

    for (auto [x, y] : pv)
        fv.add(x, y);
    for (auto [x, y] : px)
        fx.add(x, y);
    for (auto [x, y] : py)
        fy.add(x, y);
    for (auto [x, y] : cvv)
        cv.add(x, y);


}

int colour(int ar, int ac, int br, int bc) {
    int x1 = ar, y1 = ac, x2 = br, y2 = bc;
    --x1, --y1;
    --x2, --y2;
    int C = 1;
    ll E = (x2 - x1) * 2 + (y2 - y1) * 2 + fx.get(x1 + 1, y1, x2 - 1, y2 - 1) + fy.get(x1, y1 + 1, x2 - 1, y2 - 1);
    assert(E >= 0);
    ll V = (x2 - x1 + 1) * 2 + (y2 - y1 - 1) * 2 + fv.get(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    assert(V >= 0);
    ll U = cv.get(x1, y1, x2 - 1, y2 - 1);
    assert(U >= 0);
    ll F = C + 1 + E - V;
    assert(F >= 0);
    int ans = F - U - 1;
    assert(ans >= 0);
    return ans;
}

Subtask #1
0 / 11.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 126 ms 4276 KB Output is correct
4 Correct 202 ms 7212 KB Output is correct
5 Correct 223 ms 7612 KB Output is correct
6 Correct 190 ms 8020 KB Output is correct
7 Correct 178 ms 6212 KB Output is correct
8 Correct 57 ms 1900 KB Output is correct
9 Correct 203 ms 7356 KB Output is correct
10 Correct 206 ms 7436 KB Output is correct
11 Correct 203 ms 8088 KB Output is correct
12 Correct 116 ms 6624 KB Output is correct
13 Correct 133 ms 7432 KB Output is correct
14 Correct 135 ms 7448 KB Output is correct
15 Correct 145 ms 8156 KB Output is correct
16 Correct 151 ms 5916 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 206 ms 85604 KB Output is correct
3 Correct 168 ms 78112 KB Output is correct
4 Correct 287 ms 89464 KB Output is correct
5 Correct 159 ms 77032 KB Output is correct
6 Correct 150 ms 69956 KB Output is correct
7 Incorrect 218 ms 74220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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