oj.uz

답안 #820118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
820118 2023-08-10T19:46:00 Z Ahmed57 무지개나라 (APIO17_rainbow) C++17
0 / 100
 55 ms 83912 KB 
#include <bits/stdc++.h>

using namespace std;
#define M ((L+R)/2)
const int MAXN = 200000;
const int SIZE = (6e3+9)*19+1;

struct pres{
set<int> s[MAXN+5];
void add(int x,int y){
    s[x].insert(y);
}
int root[MAXN+5];
void bld(){
    root[1] = build();
    for(int i = 1;i<=MAXN;i++){
        root[i+1] = root[i];
        for(auto j:s[i]){
            int vl = query(j,j,root[i+1]);vl++;
            root[i+1] = update(j,root[i+1],vl);
        }
    }
}
int qry(int l,int r,int L,int R){
    if(r>R)return 0;
    return query(r,R,root[L+1])-(l?query(r,R,root[l]):0);
}
int l[SIZE], r[SIZE], st[SIZE], NODES = 0;
int n;
int newleaf(int value) {
    int p = ++NODES;
    l[p] = r[p] = 0; // null
    st[p] = value;
    return p;
}
int newparent(int lef, int rig) {
    int p = ++NODES;
    l[p] = lef;
    r[p] = rig;
    st[p] = st[lef] + st[rig]; // immediately update value from children
    return p;
}
int update(int i,int p,int x, int L=1, int R=MAXN) {
    if (L == R)return newleaf(x);
    if (i <= M)return newparent(update(i,l[p],x, L, M), r[p]);
    else return newparent(l[p], update(i,r[p],x, M + 1, R));
}
int build(int L=1, int R=MAXN) {
    if (L == R) return newleaf(0); // construct as leaf
    else return newparent(build(L, M),build(M+1,R)); // construct as parent
}
int query(int lq,int rq,int p,int L = 1,int R = MAXN){
    if(L>=lq&&R<=rq)return st[p];
    if(L>rq||R<lq)return 0;
    return query(lq,rq,l[p],L,M)+query(lq,rq,r[p],M+1,R);
}
}ver,edgehorz,edgevert,rivers;
void add_river(int x,int y){
    rivers.add(x,y);
    ver.add(x,y);
    ver.add(x+1,y);
    ver.add(x,y+1);
    ver.add(x+1,y+1);
    edgehorz.add(x,y);
    edgehorz.add(x+1,y);
    edgevert.add(x,y);
    edgevert.add(x,y+1);
}
int mxr ,mnr,mxc,mnc;
void init(int R, int C, int sr, int sc, int MM, char *S) {
    add_river(sr,sc);
    mxr = sr,mnr = sr,mxc = sc,mnc = sc;
    for(int i = 0;i<MM;i++){
        if(S[i]=='N')sr--;
        if(S[i]=='S')sr++;
        if(S[i]=='W')sc--;
        if(S[i]=='E')sc++;
        //cout<<sr<<" "<<sc<<endl;
        add_river(sr,sc);
        mxr = max(mxr,sr);
        mnr = min(mnr,sr);
        mxc = max(mxc,sc);
        mnc = min(mnc,sc);
    }
    rivers.bld();ver.bld();
    edgehorz.bld();edgevert.bld();
}
int colour(int ar, int ac, int br, int bc) {
    int E = edgehorz.qry(ar + 1, br, ac, bc) + edgevert.qry(ar, br, ac + 1, bc);
    int V = ver.qry(ar + 1, br, ac + 1, bc);
    int R = rivers.qry(ar, br, ac, bc);
    //cout<<R<<endl;
    int C = (ar >= mnr || br <= mxr || ac >= mnc || bc <= mxc ? 1 : 2);
    return E - V + C - R;
}/*
int main(){
    init(6, 4,
3, 3, 9,
"NWESSWEWS");
cout<<colour(1,2,5,3);
}*/

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 52 ms 83912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 51 ms 83776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 55 ms 83776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 52 ms 83912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 52 ms 83912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -