제출 #990301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990301		User0069	무지개나라 (APIO17_rainbow)	C++17	12 / 100	923 ms	639828 KiB

rainbow

#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";
//
//}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26