제출 #683370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683370		fatemetmhr	무지개나라 (APIO17_rainbow)	C++17	12 / 100	299 ms	190448 KiB

rainbow

// ~ 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
*/

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26