oj.uz

답안 #678868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678868 2023-01-06T19:24:58 Z qwerasdfzxcl 무지개나라 (APIO17_rainbow) C++17
0 / 100
 1274 ms 1048576 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9+100;

struct Node{
    int l, r, x;
    Node(){}
    Node(int _l, int _r, int _x): l(_l), r(_r), x(_x) {}
};

struct PST{
    vector<Node> tree;
    vector<int> root;
    int sz;

    int cp(int x){
        tree.push_back(tree[x]);
        return (int)tree.size()-1;
    }
    void init(int n){
        sz = n;
        tree.emplace_back(0, 0, 0);
        root.push_back(0);
    }
    void update(int i, int l, int r, int p, int x){
        if (l==r) {tree[i].x += x; return;}

        int m = (l+r)>>1;
        update(tree[i].l = cp(tree[i].l), l, m, p, x);
        update(tree[i].r = cp(tree[i].r), m+1, r, p, x);

        tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
    }
    int query(int i, int l, int r, int s, int e){
        if (r<s || e<l) return 0;
        if (s<=l && r<=e) return tree[i].x;

        int m = (l+r)>>1;
        return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
    }

    void add_root(){root.push_back(cp(root.back()));}
    void update(int p, int x){update(root.back(), 1, sz, p, x);}
    int query(int t, int l, int r){return query(root[t], 1, sz, l, r);}
    int query2D(int t1, int t2, int l, int r){return query(t2, l, r) - query(t1-1, l, r);}

}treeV, treeEh, treeEv, treeF;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, n, m, mnx, mxx, mny, mxy;
vector<int> V[200200], Eh[200200], Ev[200200], F[200200];

void add_vertex(int x, int y){
    mnx = min(mnx, x);
    mxx = max(mxx, x);
    mny = min(mny, y);
    mxy = max(mxy, y);

    V[x].push_back(y);

    Eh[x].push_back(y-1);
    Eh[x].push_back(y);
    Ev[x-1].push_back(y);
    Ev[x].push_back(y);

    for (int i=-1;i<=0;i++){
        for (int j=-1;j<=0;j++){
            F[x+i].push_back(y+j);
        }
    }
}

void pst_init(vector<int> a[], PST &tree){
    tree.init(m);
    for (int i=1;i<=n;i++){
        sort(a[i].begin(), a[i].end());
        a[i].erase(unique(a[i].begin(), a[i].end()), a[i].end());

        tree.add_root();
        for (auto &y:a[i]) if (y>0) tree.update(y, 1);
    }
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    mnx = mny = 1e9;
    mxx = mxy = -1e9;
    add_vertex(sr, sc);

    for (int i=0;i<M;i++){
        int k;
        if (S[i]=='N') k = 0;
        if (S[i]=='E') k = 1;
        if (S[i]=='S') k = 2;
        if (S[i]=='W') k = 3;

        sr += dx[k], sc += dy[k];
        add_vertex(sr, sc);
    }

    pst_init(V, treeV);
    pst_init(Eh, treeEh);
    pst_init(Ev, treeEv);
    pst_init(F, treeF);
}


int colour(int ar, int ac, int br, int bc) {
    ll v = 0, e = 0, f = 0;
    if (ar < mnx && mxx < br && ac < mny && mxy < bc) f = 1;

    ll xL = br - ar, yL = bc - ac;

    v = xL * yL - treeV.query2D(ar, br, ac, bc);
    e = xL * (yL-1) - treeEh.query2D(ar, br, ac, bc-1);
    e += (xL-1) * yL - treeEv.query2D(ar, br-1, ac, bc);
    f += (xL-1) * (yL-1) - treeF.query2D(ar, br-1, ac, bc-1);

    return v - e + f;
}

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:99:32: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |         sr += dx[k], sc += dy[k];
      |                            ~~~~^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 19668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 19112 KB Output is correct
2 Runtime error 1274 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 19668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 19668 KB Output isn't correct
2 Halted 0 ms 0 KB -