oj.uz

Submission #683370

# Submission time Handle Problem Language Result Execution time Memory
683370 2023-01-18T09:24:57 Z fatemetmhr Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 299 ms 190448 KB 
// ~ Be Name Khoda ~

#include "rainbow.h"
#include<bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  2e5   + 10;
const int maxnt =  8e5   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

struct segment_tree{

    vector <int> ini[maxn5], av[maxnt];

    void build(int l, int r, int v){
        if(r - l == 1){
            sort(all(ini[l]));
            for(auto u : ini[l])
                av[v].pb(u);
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, v * 2);
        build(mid, r, v * 2 + 1);
        int pt1 = 0, pt2 = 0;
        while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
            if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
                av[v].pb(av[v * 2][pt1++]);
            else
                av[v].pb(av[v * 2 + 1][pt2++]);
        }
    }

    int get(int l, int r, int lq, int rq, int lq2, int rq2, int v){
        if(rq <= l || r <= lq || lq2 >= rq2)
            return 0;
        if(lq <= l && r <= rq){
            int pl = lower_bound(all(av[v]), lq2) - av[v].begin();
            int pr = lower_bound(all(av[v]), rq2) - av[v].begin() - 1;
            //cout << "asking for " << l << ' ' << r << ' ' << lq << ' ' << rq << ' ' << lq2 << ' ' << rq2 << ' ' << pl << ' ' << pr << ' ' << av[v].size() << endl;
            return pr - pl + 1;
        }
        int mid = (l + r) >> 1;
        return get(l, mid, lq, rq, lq2, rq2, v * 2) + get(mid, r, lq, rq, lq2, rq2, v * 2 + 1);
    }

} segriv, segof, segam, segver;


int n, m;
vector <pair<int, int>> ver, riv;
vector <pair<pair<int, int>, pair<int, int>>> ed;


inline void add_edge(int x1, int yy1, int x2, int y2){
    if(mp(x1, yy1) > mp(x2, y2)){
        swap(x1, x2);
        swap(yy1, y2);
    }
    ver.pb({x1, yy1});
    ver.pb({x2, y2});
    ed.pb({{x1, yy1}, {x2, y2}});
}

void init(int R, int C, int sr, int sc, int M, char *S){
    n = R; m = C;
    n++; m++;
    sr--; sc--;
    riv.pb({sr, sc});
    add_edge(sr, sc, sr + 1, sc);
    add_edge(sr, sc, sr, sc + 1);
    add_edge(sr, sc + 1, sr + 1, sc + 1);
    add_edge(sr + 1, sc, sr + 1, sc + 1);
    for(int i = 0; i < M; i++){
        if(S[i] == 'N')
            sr--;
        if(S[i] == 'S')
            sr++;
        if(S[i] == 'E')
            sc++;
        if(S[i] == 'W')
            sc--;
        riv.pb({sr, sc});
        add_edge(sr, sc, sr + 1, sc);
        add_edge(sr, sc, sr, sc + 1);
        add_edge(sr, sc + 1, sr + 1, sc + 1);
        add_edge(sr + 1, sc, sr + 1, sc + 1);
    }
    sort(all(riv)); sort(all(ver)); sort(all(ed));
    riv.resize(unique(all(riv)) - riv.begin());
    ver.resize(unique(all(ver)) - ver.begin());
    ed.resize(unique(all(ed)) - ed.begin());
    for(auto [x, y] : riv){
        segriv.ini[x].pb(y);
        //cout << "river of " << x << ' ' << y << endl;
    }
    for(auto [x, y] : ver)
        segver.ini[x].pb(y);
    for(auto [p1, p2] : ed){
        if(p1.fi == p2.fi)
            segof.ini[p1.fi].pb(min(p1.se, p2.se));
        else
            segam.ini[min(p1.fi, p2.fi)].pb(p1.se);
    }
    segriv.build(0, n, 1);
    segver.build(0, n, 1);
    segof.build(0, n, 1);
    segam.build(0, n, 1);
}

int colour(int ax, int ay, int bx, int by){
    ax--; ay--; bx--; by--;
    ll nover = 4 + 2 * (bx - ax + by - ay), noed = 2 * (bx - ax + by - ay + 2), noriv = 0;
    if(ax < bx && ay < by)
        nover += segver.get(0, n, ax + 1, bx + 1, ay + 1, by + 1, 1);
    if(ax < bx)
        noed += segof.get(0, n, ax + 1, bx + 1, ay, by + 1, 1);
    if(ay < by)
        noed += segam.get(0, n, ax, bx + 1, ay + 1, by + 1, 1);
    noriv = segriv.get(0, n, ax, bx + 1, ay, by + 1, 1);
    return noed - nover + 1 - noriv;
}

/*
6 4 9 1
3 3
NWESSWEWS
1 2 5 3
2 3 2 3
3 2 4 4
5 3 6 4
*/

Compilation message

rainbow.cpp: In member function 'void segment_tree::build(int, int, int)':
rainbow.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
      |               ~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:41:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         while(pt1 < av[v * 2].size() || pt2 < av[v * 2 + 1].size()){
      |                                         ~~~~^~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
      |                ~~~~^~~~~~~~~~~~~~~~~~
rainbow.cpp:42:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if(pt1 < av[v * 2].size() && (pt2 == av[v * 2 + 1].size() || av[v * 2][pt1] < av[v * 2 + 1][pt2]))
      |                                           ~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94232 KB Output is correct
2 Correct 57 ms 94620 KB Output is correct
3 Incorrect 46 ms 94340 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 44 ms 94220 KB Output is correct
2 Correct 45 ms 94224 KB Output is correct
3 Correct 191 ms 111752 KB Output is correct
4 Correct 278 ms 121652 KB Output is correct
5 Correct 261 ms 121532 KB Output is correct
6 Correct 270 ms 119504 KB Output is correct
7 Correct 289 ms 118800 KB Output is correct
8 Correct 186 ms 112132 KB Output is correct
9 Correct 276 ms 121584 KB Output is correct
10 Correct 290 ms 121688 KB Output is correct
11 Correct 272 ms 119456 KB Output is correct
12 Correct 225 ms 120364 KB Output is correct
13 Correct 217 ms 121676 KB Output is correct
14 Correct 212 ms 121476 KB Output is correct
15 Correct 236 ms 119616 KB Output is correct
16 Correct 216 ms 115136 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94148 KB Output is correct
2 Correct 214 ms 155720 KB Output is correct
3 Correct 299 ms 190448 KB Output is correct
4 Correct 258 ms 178700 KB Output is correct
5 Correct 230 ms 159916 KB Output is correct
6 Correct 174 ms 118180 KB Output is correct
7 Incorrect 204 ms 128292 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94232 KB Output is correct
2 Correct 57 ms 94620 KB Output is correct
3 Incorrect 46 ms 94340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94232 KB Output is correct
2 Correct 57 ms 94620 KB Output is correct
3 Incorrect 46 ms 94340 KB Output isn't correct
4 Halted 0 ms 0 KB -