oj.uz

Submission #557058

# Submission time Handle Problem Language Result Execution time Memory
557058 2022-05-04T16:44:27 Z nutella Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1229 ms 153856 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

struct Fenwick {
    unordered_map<int, unordered_map<int, ll>> t;
    int n, m;
    set<pii > stt;

    Fenwick(int a, int b) {
        n = a, m = b;
    }

    Fenwick() = default;

    void build(int a, int b) {
        n = a, m = b;
    }

    void add(int x, int y, int val) {
        if (stt.count(mp(x, y))) return;
        stt.insert(mp(x, y));
        for (int i = x; i < n; i |= (i + 1))
            for (int j = y; j < m; j |= (j + 1))
                t[i][j] += val;
    }

    ll get(int x, int y) {
        ll ans = 0;
        for (int i = x; i > -1; i = ((i + 1) & i) - 1)
            for (int j = y; 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>>
        river,
        yy;
Fenwick fx, fy, fv, cv;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R + 1, m = C + 1;
    --sr, --sc;
    fx.build(n, m), fy.build(n, m), fv.build(n, m), cv.build(n, m);
    river = {{sr, sc}};
    set<pii > used;
    used.insert(mp(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;
        river.emplace_back(sr, sc);
    }
    yy = river;
    sort(all(yy));
    yy.resize(unique(all(yy)) - begin(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);
    };

    for (auto [x, y]: yy) {
        fv.add(x, y, 1);
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (here(nx, ny)) {
                if (nx == x) {
                    fx.add(x, min(ny, y), 1);
                } else {
                    fy.add(min(nx, x), y, 1);
                }
            }
        }
        if (here(x + 1, y) && here(x, y + 1) && here(x + 1, y + 1)) {
            cv.add(x, y, 1);
        }
    }

}

// ans = F - F(river);
// F(river) = C(river) = V(river) - E(river)
// F = C + 1 + E - V
// C is 2 if river is completely inside our rectangle, otherwise C = 1


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);
    ll V = (x2 - x1 + 1) * 2 + (y2 - y1 - 1) * 2 + fv.get(x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    ll U = cv.get(x1, y1, x2 - 1, y2 - 1);
    ll F = C + 1 + E - V;
    return (int) (F - U -1);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 340 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 728 ms 41148 KB Output is correct
4 Correct 845 ms 55372 KB Output is correct
5 Correct 884 ms 59104 KB Output is correct
6 Correct 942 ms 60512 KB Output is correct
7 Correct 685 ms 37132 KB Output is correct
8 Correct 640 ms 35896 KB Output is correct
9 Correct 837 ms 50768 KB Output is correct
10 Correct 849 ms 51428 KB Output is correct
11 Correct 898 ms 52312 KB Output is correct
12 Correct 258 ms 25572 KB Output is correct
13 Correct 293 ms 29020 KB Output is correct
14 Correct 324 ms 30240 KB Output is correct
15 Correct 359 ms 29456 KB Output is correct
16 Correct 772 ms 53988 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 827 ms 83120 KB Output is correct
3 Correct 591 ms 101700 KB Output is correct
4 Correct 1229 ms 153856 KB Output is correct
5 Correct 651 ms 80260 KB Output is correct
6 Correct 342 ms 12172 KB Output is correct
7 Incorrect 609 ms 20764 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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