제출 #52639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52639		gs18115	허수아비 (JOI14_scarecrows)	C++14	100 / 100	665 ms	149688 KiB

scarecrows

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#define FI first
#define SE second
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<LL,LL>PL;
typedef vector<LL>VL;
typedef set<LL>SL;
const LL INF=1LL<<55LL;
struct SCW
{
    LL x,y;
}x[234567],y[234567],P[234567];
bool cmp1(SCW X,SCW Y)
{
    return X.x<Y.x;
}
bool cmp2(SCW X,SCW Y)
{
    return X.x>Y.x;
}
bool cmp3(SCW X,SCW Y)
{
    return X.y<Y.y;
}
SCW min(SCW X,SCW Y)
{
    if(X.x>Y.x)
        return Y;
    return X;
}
LL N,N2,C,s,i;
SCW xmi;
vector<SCW>seg[876543];
void SUM(LL N,LL x1,LL x2,LL X1,LL X2)
{
    if(x1>x2||X1>X2||x1>X2||x2<X1)
        return;
    if(X1>=x1&&X2<=x2)
    {
        if(!seg[N].empty())
        {
            vector<SCW>::iterator it=upper_bound(seg[N].begin(),seg[N].end(),xmi,cmp2);
            xmi=min(xmi,seg[N].back());
            s+=seg[N].end()-it;
        }
        return;
    }
    LL mid=X1+X2>>1;
    SUM(N<<1,x1,x2,X1,mid);
    SUM((N<<1)+1,x1,x2,mid+1,X2);
    return;
}
void IN(LL N,SCW X)
{
    if(!seg[N].empty())
        seg[N].erase(upper_bound(seg[N].begin(),seg[N].end(),X,cmp3),seg[N].end());
    seg[N].PB(X);
    if(N<2)
        return;
    IN(N>>1,X);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>N;
    for(N2=1;N2<N;N2<<=1);
    for(i=0;i<N;i++)
    {
        cin>>x[i].x>>y[i].x;
        x[i].y=y[i].y=i;
    }
    sort(x,x+N,cmp1);
    sort(y,y+N,cmp1);
    C=0;
    P[x[0].y].x=0;
    for(i=1;i<N;i++)
        P[x[i].y].x=++C;
    C=0;
    P[y[0].y].y=0;
    for(i=1;i<N;i++)
        P[y[i].y].y=++C;
    sort(P,P+N,cmp1);
    for(i=N;i-->0;)
    {
        xmi.x=xmi.y=INF;
        SUM(1,P[i].y+1,N2-1,0,N2-1);
        IN(N2+P[i].y,P[i]);
    }
    cout<<s<<endl;
    return 0;
}

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

scarecrows.cpp: In function 'void SUM(LL, LL, LL, LL, LL)':
scarecrows.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     LL mid=X1+X2>>1;
            ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85