oj.uz

Submission #734996

# Submission time Handle Problem Language Result Execution time Memory
734996 2023-05-03T10:51:31 Z bin9638 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1762 ms 278436 KB 
#include <bits/stdc++.h>

#ifndef SKY
#include "rainbow.h"
#endif // SKY

using namespace std;

#define N 200010
#define ll long long
#define fs first
#define sc second
#define ii pair<ll,int>
#define pb push_back

int r,c,m;

struct BIT
{
    unordered_map<int,int>bit[N];
    map<int,int>mp[N];

    void update(int x,int y,int val)
    {
        x=r-x+2;
        y=c-y+2;
        for(int u=x;u>0;u-=u&(-u))
            for(int v=y;v>0;v-=v&(-v))
                bit[u][v]+=val;
    }

    int get(int x,int y)
    {
        x=r-x+2;
        y=c-y+2;
        int res=0;
        for(int u=x;u<=r+1;u+=u&(-u))
            for(int v=y;v<=c+1;v+=v&(-v))
                if(bit[u].find(v)!=bit[u].end())
                    res+=bit[u][v];
        return res;
    }

    void init(int u,int v)
    {
        if(++mp[u][v]==1)
            update(u,v,1);
    }

    int solve(int ar, int ac, int br, int bc)
    {
        if(ar>br||ac>bc)
            return 0;
        return get(br,bc)+get(ar-1,ac-1)-get(ar-1,bc)-get(br,ac-1);
    }
}row,col,p,cell;

void build(int u,int v)
{
    p.init(u,v);
    p.init(u+1,v);
    p.init(u,v+1);
    p.init(u+1,v+1);
    row.init(u,v);
    row.init(u+1,v);
    col.init(u,v);
    col.init(u,v+1);
    cell.init(u,v);
}

void init(int RRR, int CCC, int sr, int sc, int MMM, char *S)
{
    r=RRR;
    c=CCC;
    m=MMM;
    build(sr,sc);
    for(int i=1;i<=m;i++)
    {
        char ch=*S;
        if(i!=m)
            S++;
        if(ch=='N')
            sr--;
        if(ch=='S')
            sr++;
        if(ch=='E')
            sc++;
        if(ch=='W')
            sc--;
        build(sr,sc);
    }

}

int colour(int ar, int ac, int br, int bc)
{
    int res=0;
    res+=row.solve(ar+1,ac,br,bc)+col.solve(ar,ac+1,br,bc);
    res-=p.solve(ar+1,ac+1,br,bc);
    res-=cell.solve(ar,ac,br,bc);
    return res+1;
}


#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int r,c,sr,sc,m;
    string S;
    cin>>r>>c>>sr>>sc>>m>>S;
    init(r,c,sr,sc,m,&S[0]);
    int q;
    cin>>q;
    while(q--)
    {
        int ar,ac,br,bc;
        cin>>ar>>ac>>br>>bc;
        cout<<colour(ar,ac,br,bc)<<endl;
    }
    return 0;
}
#endif

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 81740 KB Output is correct
2 Correct 44 ms 82144 KB Output is correct
3 Incorrect 44 ms 81764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 81620 KB Output is correct
2 Correct 42 ms 81620 KB Output is correct
3 Correct 668 ms 119500 KB Output is correct
4 Correct 872 ms 145304 KB Output is correct
5 Correct 882 ms 144792 KB Output is correct
6 Correct 727 ms 128632 KB Output is correct
7 Correct 685 ms 127724 KB Output is correct
8 Correct 238 ms 85360 KB Output is correct
9 Correct 895 ms 145208 KB Output is correct
10 Correct 995 ms 144984 KB Output is correct
11 Correct 741 ms 128624 KB Output is correct
12 Correct 606 ms 139300 KB Output is correct
13 Correct 612 ms 145320 KB Output is correct
14 Correct 596 ms 144720 KB Output is correct
15 Correct 506 ms 128552 KB Output is correct
16 Correct 735 ms 127436 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 81612 KB Output is correct
2 Correct 1594 ms 244588 KB Output is correct
3 Correct 926 ms 247960 KB Output is correct
4 Correct 1762 ms 278436 KB Output is correct
5 Correct 971 ms 220576 KB Output is correct
6 Correct 315 ms 93900 KB Output is correct
7 Incorrect 628 ms 105044 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 81740 KB Output is correct
2 Correct 44 ms 82144 KB Output is correct
3 Incorrect 44 ms 81764 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 81740 KB Output is correct
2 Correct 44 ms 82144 KB Output is correct
3 Incorrect 44 ms 81764 KB Output isn't correct
4 Halted 0 ms 0 KB -