oj.uz

답안 #990301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990301 2024-05-30T07:06:08 Z User0069 무지개나라 (APIO17_rainbow) C++17
12 / 100
 923 ms 639828 KB 
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
int R,C,m,q;
string s;
struct node
{
    int val1,val2,val3;
    node *l,*r;
    node(): val1(0),val2(0),val3(0),l(NULL),r(NULL){};
}*rootc[maxn],*rootr[maxn];
node* cons(node* kk,int cl,int cr)
{
    if(cl==cr) return new node();
    int mid=(cl+cr)/2;
    kk=new node();
    kk->l=cons(kk->l,cl,mid);
    kk->r=cons(kk->r,mid+1,cr);
    return kk;
}
node* update(node* kk,int cl,int cr,int pos,int val,int type)
{
    node* kkk=new node();
    kkk->val1=kk->val1;
    kkk->val2=kk->val2;
    kkk->val3=kk->val3;
    kkk->l=kk->l;
    kkk->r=kk->r;
    if(cl==cr)
    {
        if(type==1) kkk->val1+=val;
        else if(type==2) kkk->val2+=val;
        else kkk->val3+=val;
        return kkk;
    }
    int mid=(cl+cr)/2;
    if(pos<=mid) kkk->l=update(kk->l,cl,mid,pos,val,type);
    else kkk->r=update(kk->r,mid+1,cr,pos,val,type);
    kkk->val1=kkk->l->val1+kkk->r->val1;
    kkk->val2=kkk->l->val2+kkk->r->val2;
    kkk->val3=kkk->l->val3+kkk->r->val3;
    return kkk;
}
int get(node* kk,int cl,int cr,int l,int r,int type)
{
    if(cl>r||cr<l) return 0;
    if(cl>=l&&cr<=r)
    {
        if(type==1) return kk->val1;
        else if(type==2) return kk->val2;
        else return kk->val3;
    }
    int mid=(cl+cr)/2;
    return get(kk->l,cl,mid,l,r,type)+get(kk->r,mid+1,cr,l,r,type);
}
set<pii> path;
set<int> row[maxn],col[maxn],blc[maxn],blr[maxn];
void init(int32_t _R,int32_t _C,int32_t SR,int32_t SC,int32_t M,char* t)
{
    R=_R;
    C=_C;
    m=M;
    path.insert({SR,SC});
    for(int i=0;i<M;i++)
    {
        char x=t[i];
        if(x=='N') SR--;
        if(x=='S') SR++;
        if(x=='E') SC++;
        if(x=='W') SC--;
        path.insert({SR,SC});
    }
    for( pii x:path)
    {
        row[x.fi].insert(x.sc);
        row[x.fi-1].insert(x.sc);
        col[x.sc].insert(x.fi);
        col[x.sc-1].insert(x.fi);
        blr[x.fi].insert(x.sc);
        blr[x.fi-1].insert(x.sc);
        blr[x.fi].insert(x.sc-1);
        blr[x.fi-1].insert(x.sc-1);
        blc[x.fi].insert(x.sc);
    }
    rootr[0]=cons(rootr[0],0,C);
    for(int i=1;i<=R;i++)
    {
        rootr[i]=rootr[i-1];
        for(int x:row[i])
        {
            rootr[i]=update(rootr[i],0,C,x,1,1);
        }
        for(int x:blc[i])
        {
            rootr[i]=update(rootr[i],0,C,x,1,2);
        }
        for(int x:blr[i])
        {
            rootr[i]=update(rootr[i],0,C,x,1,3);
        }

    }
    rootc[0]=cons(rootc[0],0,R);
    for(int i=1;i<=C;i++)
    {
        rootc[i]=rootc[i-1];
        for(int x:col[i])
        {
            rootc[i]=update(rootc[i],0,R,x,1,1);
        }
    }
}
int colour(int32_t ar,int32_t ac,int32_t br,int32_t bc)
{
    int border=2*(br-ar+bc-ac+2);
    int rr=get(rootr[br-1],0,C,ac,bc,1)-get(rootr[ar-1],0,C,ac,bc,1);
    int cc=get(rootc[bc-1],0,R,ar,br,1)-get(rootc[ac-1],0,R,ar,br,1);
    int block=get(rootr[br],0,C,ac,bc,2)-get(rootr[ar-1],0,C,ac,bc,2);
    int vert=get(rootr[br-1],0,C,ac,bc-1,3)-get(rootr[ar-1],0,C,ac,bc-1,3);
    return rr+cc+2-block-vert-1;
    return 0;
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname".OUT","w",stdout);
//    }
//    Faster
//    init(6, 4, 3, 3, 9,"NWESSWEWS");
//    cout<<colour(2,3,2,3)<<"\n";
//    cout<<colour(3,2,4,4)<<"\n";
//    cout<<colour(5,3,6,4)<<"\n";
//    cout<<colour(1,2,5,3)<<"\n";
//
//}

Compilation message

rainbow.cpp: In function 'll colour(int32_t, int32_t, int32_t, int32_t)':
rainbow.cpp:129:9: warning: unused variable 'border' [-Wunused-variable]
  129 |     int border=2*(br-ar+bc-ac+2);
      |         ^~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39772 KB Output is correct
2 Correct 8 ms 41412 KB Output is correct
3 Incorrect 8 ms 40028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 39512 KB Output is correct
2 Correct 6 ms 39600 KB Output is correct
3 Correct 535 ms 305908 KB Output is correct
4 Correct 923 ms 458584 KB Output is correct
5 Correct 748 ms 446512 KB Output is correct
6 Correct 577 ms 341416 KB Output is correct
7 Correct 561 ms 320592 KB Output is correct
8 Correct 269 ms 63480 KB Output is correct
9 Correct 684 ms 456044 KB Output is correct
10 Correct 751 ms 445264 KB Output is correct
11 Correct 584 ms 341636 KB Output is correct
12 Correct 567 ms 449628 KB Output is correct
13 Correct 568 ms 457812 KB Output is correct
14 Correct 561 ms 447240 KB Output is correct
15 Correct 442 ms 341840 KB Output is correct
16 Correct 567 ms 322128 KB Output is correct

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 39516 KB Output is correct
2 Correct 637 ms 636536 KB Output is correct
3 Correct 518 ms 631632 KB Output is correct
4 Correct 508 ms 639828 KB Output is correct
5 Correct 411 ms 494620 KB Output is correct
6 Correct 147 ms 184148 KB Output is correct
7 Incorrect 242 ms 289108 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39772 KB Output is correct
2 Correct 8 ms 41412 KB Output is correct
3 Incorrect 8 ms 40028 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 39772 KB Output is correct
2 Correct 8 ms 41412 KB Output is correct
3 Incorrect 8 ms 40028 KB Output isn't correct
4 Halted 0 ms 0 KB -