oj.uz

Submission #155189

# Submission time Handle Problem Language Result Execution time Memory
155189 2019-09-26T23:59:21 Z arnold518 Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 320 ms 139648 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct SEG
{
    vector<int> tree[MAXN*4+10];

    void push(int node, int tl, int tr, int pos, int val)
    {
        if(tl==tr) { tree[node].push_back(val); return; }
        int mid=tl+tr>>1;
        if(pos<=mid) push(node*2, tl, mid, pos, val);
        else push(node*2+1, mid+1, tr, pos, val);
    }

    void init(int node, int tl, int tr)
    {
        if(tl==tr)
        {
            sort(tree[node].begin(), tree[node].end());
            return;
        }
        int mid=tl+tr>>1;
        init(node*2, tl, mid);
        init(node*2+1, mid+1, tr);
        tree[node].resize(tree[node*2].size()+tree[node*2+1].size());
        merge(tree[node*2].begin(), tree[node*2].end(), tree[node*2+1].begin(), tree[node*2+1].end(), tree[node].begin());
    }

    int query(int node, int tl, int tr, int xl, int xr, int yl, int yr)
    {
        if(xr<tl || tr<xl) return 0;
        if(xl<=tl && tr<=xr) return upper_bound(tree[node].begin(), tree[node].end(), yr)-lower_bound(tree[node].begin(), tree[node].end(), yl);
        int mid=tl+tr>>1;
        return query(node*2, tl, mid, xl, xr, yl, yr)+query(node*2+1, mid+1, tr, xl, xr, yl, yr);
    }
};
SEG segv, sege1, sege2, segf;

int R, C;

void init(int _R, int _C, int sy, int sx, int M, char *S)
{
    int i, j;
    R=_R; C=_C;

    vector<pii> T, TT;
    T.push_back({sx, sy});
    T.push_back({sx, sy-1});
    T.push_back({sx-1, sy});
    T.push_back({sx-1, sy-1});
    TT.push_back({sx, sy});
    for(i=0; i<M; i++)
    {
        if(S[i]=='N') sy--;
        if(S[i]=='W') sx--;
        if(S[i]=='S') sy++;
        if(S[i]=='E') sx++;
        T.push_back({sx, sy});
        if(sy-1>0) T.push_back({sx, sy-1});
        if(sx-1>0) T.push_back({sx-1, sy});
        if(sx-1>0 && sy-1>0) T.push_back({sx-1, sy-1});
        TT.push_back({sx, sy});
    }
    sort(T.begin(), T.end());
    T.erase(unique(T.begin(), T.end()), T.end());

    sort(TT.begin(), TT.end());
    TT.erase(unique(TT.begin(), TT.end()), TT.end());

    for(auto it : TT) segv.push(1, 1, C, it.first, it.second);
    for(auto it : T) if(binary_search(TT.begin(), TT.end(), pii(it.first, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first, it.second+1))) sege1.push(1, 1, C, it.first, it.second);
    for(auto it : T) if(binary_search(TT.begin(), TT.end(), pii(it.first, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first+1, it.second))) sege2.push(1, 1, C, it.first, it.second);
    for(auto it : T) if(binary_search(TT.begin(), TT.end(), pii(it.first, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first+1, it.second)) || binary_search(TT.begin(), TT.end(), pii(it.first, it.second+1)) || binary_search(TT.begin(), TT.end(), pii(it.first+1, it.second+1))) segf.push(1, 1, C, it.first, it.second);

    segv.init(1, 1, C);
    sege1.init(1, 1, C);
    sege2.init(1, 1, C);
    segf.init(1, 1, C);
}

int colour(int Y1, int X1, int Y2, int X2)
{
    ll v, e1, e2, f;
    v=(ll)(Y2-Y1+1)*(X2-X1+1)-segv.query(1, 1, C, X1, X2, Y1, Y2);
    e1=(ll)(Y2-Y1)*(X2-X1+1)-sege1.query(1, 1, C, X1, X2, Y1, Y2-1);
    e2=(ll)(Y2-Y1+1)*(X2-X1)-sege2.query(1, 1, C, X1, X2-1, Y1, Y2);
    f=(ll)(Y2-Y1)*(X2-X1)-segf.query(1, 1, C, X1, X2-1, Y1, Y2-1);

    //printf("%lld %lld %lld %lld\n", v, e1, e2, f);
    //printf("============================================\n");
    return v-e1-e2+f;
}

Compilation message

rainbow.cpp: In member function 'void SEG::push(int, int, int, int, int)':
rainbow.cpp:18:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In member function 'void SEG::init(int, int, int)':
rainbow.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In member function 'int SEG::query(int, int, int, int, int, int, int)':
rainbow.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid=tl+tr>>1;
                 ~~^~~
rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:51:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 75512 KB Output is correct
2 Correct 87 ms 75820 KB Output is correct
3 Incorrect 71 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 75484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 75500 KB Output is correct
2 Correct 320 ms 139648 KB Output is correct
3 Correct 225 ms 122848 KB Output is correct
4 Correct 298 ms 129712 KB Output is correct
5 Correct 215 ms 115680 KB Output is correct
6 Correct 149 ms 88028 KB Output is correct
7 Incorrect 169 ms 96220 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 75512 KB Output is correct
2 Correct 87 ms 75820 KB Output is correct
3 Incorrect 71 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 75512 KB Output is correct
2 Correct 87 ms 75820 KB Output is correct
3 Incorrect 71 ms 75512 KB Output isn't correct
4 Halted 0 ms 0 KB -