oj.uz

Submission #765541

# Submission time Handle Problem Language Result Execution time Memory
765541 2023-06-24T18:45:30 Z bin9638 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 1121 ms 278236 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)
{
    if(cell.solve(ar,ac,br,bc)==0)
        return 1;
    int res=0;
    res+=row.solve(ar+1,ac,br,bc)+col.solve(ar,ac+1,br,bc);
   // cout<<res<<endl;
    res-=p.solve(ar+1,ac+1,br,bc);
 //   cout<<p.solve(ar+1,ac+1,br,bc)<<endl;
    res-=cell.solve(ar,ac,br,bc);
    if(cell.solve(ar,ac,ar,bc)>0||cell.solve(br,ac,br,bc)>0||cell.solve(ar,ac,br,ac)>0||cell.solve(ar,bc,br,bc)>0)
        return res+1;
    return 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 81716 KB Output is correct
2 Correct 44 ms 82236 KB Output is correct
3 Incorrect 40 ms 81868 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 38 ms 81612 KB Output is correct
2 Correct 37 ms 81644 KB Output is correct
3 Correct 493 ms 119576 KB Output is correct
4 Correct 781 ms 145124 KB Output is correct
5 Correct 792 ms 144884 KB Output is correct
6 Correct 528 ms 128776 KB Output is correct
7 Correct 511 ms 127740 KB Output is correct
8 Correct 198 ms 85384 KB Output is correct
9 Correct 797 ms 145216 KB Output is correct
10 Correct 735 ms 144796 KB Output is correct
11 Correct 542 ms 128556 KB Output is correct
12 Correct 484 ms 139352 KB Output is correct
13 Correct 514 ms 145048 KB Output is correct
14 Correct 479 ms 144740 KB Output is correct
15 Correct 409 ms 128656 KB Output is correct
16 Correct 612 ms 127532 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 81620 KB Output is correct
2 Correct 959 ms 244580 KB Output is correct
3 Correct 598 ms 247852 KB Output is correct
4 Correct 1121 ms 278236 KB Output is correct
5 Correct 606 ms 220488 KB Output is correct
6 Correct 186 ms 93960 KB Output is correct
7 Incorrect 331 ms 104788 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 81716 KB Output is correct
2 Correct 44 ms 82236 KB Output is correct
3 Incorrect 40 ms 81868 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 81716 KB Output is correct
2 Correct 44 ms 82236 KB Output is correct
3 Incorrect 40 ms 81868 KB Output isn't correct
4 Halted 0 ms 0 KB -