oj.uz

답안 #1028418

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1028418 2024-07-19T19:59:15 Z _8_8_ 무지개나라 (APIO17_rainbow) C++17
35 / 100
 3000 ms 210708 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
 
using namespace std;
 
vector<pair<int,int>> pts;
struct segtr{
    vector<int> t;
    int n;
    void init(int s){
        n = s;
        t.assign((s + 1) * 4,0);
    }
    void upd(int pos,int val,int v,int tl,int tr){
        t[v] += val;
        if(tl == tr){
            return;
        }
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd(pos,val,v+v,tl,tm);
        else upd(pos,val,v+v+1,tm+1,tr);
    }
    int get(int l,int r,int v,int tl,int tr){
        if(l > r || tl >r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
};

struct dd{
    vector<vector<int>> f,t;
    vector<segtr> b;
    int n;
    void build(int v,int tl,int tr){
        if(tl == tr){
            t[v] = f[tl];
            t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
            // cerr << (int)t[v].size() << '\n';
            b[v].init((int)t[v].size());
        }else{
            int tm = (tl + tr) >> 1;
            build(v+v,tl,tm);
            build(v + v + 1,tm + 1,tr);
            t[v].resize((int)t[v+v].size() + (int)t[v +v + 1].size());
            merge(t[v + v].begin(),t[v + v].end(),t[v + v + 1].begin(),t[v + v + 1].end(),t[v].begin());
            t[v].resize(unique(t[v].begin(),t[v].end()) - t[v].begin());
            b[v].init((int)t[v].size());
        }
    }
    void init(int s,vector<vector<int>> _f){
        n = s;
        t.resize((n + 1) * 4);
        b.resize((n+1)*4);
        f = _f;
        build(1,1,n);
    }
    void upd(int x,int y,int val,int v,int tl,int tr){
        int it = lower_bound(t[v].begin(),t[v].end(),y)-t[v].begin()+1;
        b[v].upd(it,val,1,1,b[v].n);
        if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        if(x <= tm) upd(x,y,val,v+v,tl,tm);
        else upd(x,y,val,v+v+1,tm+1,tr);
    }
    int get(int l,int r,int l1,int r1,int v,int tl,int tr){
        // return 0;
        if(l > r || tl > r || l > tr) return 0;
        if(tl >= l && tr <= r){
            int it = lower_bound(t[v].begin(),t[v].end(),l1)-t[v].begin()+1;
            int it1 = upper_bound(t[v].begin(),t[v].end(),r1)-t[v].begin();
            return b[v].get(it,it1,1,1,b[v].n);
        }
        int tm =(tl+tr)>>1;
        return get(l,r,l1,r1,v+v,tl,tm)+get(l,r,l1,r1,v+v+1,tm+1,tr);
    }
}ver;
void init(int R, int C, int sr, int sc, int M, char *S) {
    pts.push_back({sr,sc});
    vector<vector<int>> f(R+1);
    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++;
        }
        assert(sr <= R && sr >= 1);
        assert(sc <= C && sc >= 1);
        pts.push_back({sr,sc});
    }
    sort(pts.begin(),pts.end());
    pts.resize(unique(pts.begin(),pts.end()) - pts.begin());
    for(auto [x,y]:pts){
        f[x].push_back(y);
    }
    ver.init(R,f);
    for(auto [x,y]:pts){
        ver.upd(x,y,1,1,1,ver.n);
    }
}
const int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
map<pair<int,int>,bool> k,vis;
int colour(int ar, int ac, int br, int bc) {
k.clear();
    vis.clear();
    int V = 0,E = 0;
    bool ok  =true;
    for(auto [r,c]:pts){
        if(r >= ar && r <= br && c >= ac && c <= bc){
            k[{r,c}] = 1;
            if(r == ar || r == br || c == ac || c == bc){
                ok=false;
            }
        }
    }
    if(k.empty()){
        ok=false;
    }
    for(int i = ar - 1;i <= br + 1;i++){
        k[{i,ac-1}] = k[{i,bc+1}] = 1;
    }
    for(int i = ac - 1;i <= bc + 1;i++){
        k[{ar-1,i}] = k[{br+1,i}] = 1;
    }
    int bf = 0;
    for(auto [xx,_y]:k){
        auto [r,c] = xx;
        if(k.count({r + 1,c}) && k.count({r,c + 1}) && k.count({r + 1,c + 1})){
            bf++;
        }
        if(k.count({r+1,c+1}) && !k.count({r+1,c}) && !k.count({r,c+1})){
            E += 2;
        }
        if(k.count({r+1,c-1}) && !k.count({r+1,c}) && !k.count({r,c-1})){
            E += 2;
        }
        if(!vis.count({r,c})){
            queue<pair<int,int>> q;
            q.push({r,c});
            vis[{r,c}]=1;
            while(!q.empty()){
                V++;
                auto [x,y] = q.front();q.pop();
                // cout << x << ' ' << y << '\n';
                for(int i = 0;i < 4;i++){
                    int _x = x + dx[i],_y = y + dy[i];
                    if(k.count({_x,_y})){
                        E++;
                    }
                    if(k.count({_x,_y}) && !vis.count({_x,_y})){
                        vis[{_x,_y}]=1;
                        q.push({_x,_y});
                    }
                }
            }
        }
    }
    assert(E%2==0);
    E /= 2; 
    // cout << V << ' ' << -ver.get(ar,br,ac,bc,1,1,ver.n)-(br-ar+3)*2-(bc-ac+1)*2 <<  '\n';
    return  -ver.get(ar,br,ac,bc,1,1,ver.n)-(br-ar+3)*2-(bc-ac+1)*2 + E - bf + 1+ok;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 500 KB Output is correct
2 Correct 126 ms 636 KB Output is correct
3 Correct 81 ms 344 KB Output is correct
4 Correct 105 ms 344 KB Output is correct
5 Correct 198 ms 604 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 448 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 168 ms 572 KB Output is correct
12 Correct 287 ms 604 KB Output is correct
13 Correct 328 ms 600 KB Output is correct
14 Correct 553 ms 864 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 3068 ms 56132 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 700 ms 141960 KB Output is correct
3 Correct 599 ms 119056 KB Output is correct
4 Correct 584 ms 123672 KB Output is correct
5 Correct 315 ms 97556 KB Output is correct
6 Correct 842 ms 125584 KB Output is correct
7 Correct 1389 ms 154748 KB Output is correct
8 Correct 65 ms 11188 KB Output is correct
9 Correct 52 ms 9408 KB Output is correct
10 Correct 68 ms 37968 KB Output is correct
11 Correct 142 ms 44916 KB Output is correct
12 Correct 310 ms 111640 KB Output is correct
13 Correct 241 ms 90564 KB Output is correct
14 Correct 313 ms 99864 KB Output is correct
15 Correct 274 ms 91088 KB Output is correct
16 Correct 724 ms 113268 KB Output is correct
17 Correct 701 ms 110288 KB Output is correct
18 Correct 969 ms 129816 KB Output is correct
19 Correct 980 ms 148676 KB Output is correct
20 Correct 759 ms 136440 KB Output is correct
21 Correct 307 ms 28100 KB Output is correct
22 Correct 244 ms 24528 KB Output is correct
23 Correct 403 ms 61560 KB Output is correct
24 Correct 614 ms 78176 KB Output is correct
25 Correct 1760 ms 210708 KB Output is correct
26 Correct 1622 ms 187680 KB Output is correct
27 Correct 1629 ms 199068 KB Output is correct
28 Correct 1612 ms 187040 KB Output is correct
29 Correct 1600 ms 166444 KB Output is correct
30 Correct 1663 ms 171604 KB Output is correct
31 Correct 1649 ms 181012 KB Output is correct
32 Correct 1701 ms 199308 KB Output is correct
33 Correct 1744 ms 199052 KB Output is correct

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 500 KB Output is correct
2 Correct 126 ms 636 KB Output is correct
3 Correct 81 ms 344 KB Output is correct
4 Correct 105 ms 344 KB Output is correct
5 Correct 198 ms 604 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 448 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 168 ms 572 KB Output is correct
12 Correct 287 ms 604 KB Output is correct
13 Correct 328 ms 600 KB Output is correct
14 Correct 553 ms 864 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3053 ms 9416 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 500 KB Output is correct
2 Correct 126 ms 636 KB Output is correct
3 Correct 81 ms 344 KB Output is correct
4 Correct 105 ms 344 KB Output is correct
5 Correct 198 ms 604 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 448 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 168 ms 572 KB Output is correct
12 Correct 287 ms 604 KB Output is correct
13 Correct 328 ms 600 KB Output is correct
14 Correct 553 ms 864 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Execution timed out 3053 ms 9416 KB Time limit exceeded
19 Halted 0 ms 0 KB -