oj.uz

답안 #51687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51687 2018-06-20T02:07:23 Z Retro3014 허수아비 (JOI14_scarecrows) C++17
0 / 100
 487 ms 14620 KB 
#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_N 200003
#define INF 2000000000
using namespace std;

int seg[MAX_N*4+1];
bool chk[MAX_N*4+1];

struct S{
    int x, y;
};
bool sf1(S a, S b){
    return a.x<b.x;
}
bool sf2(S a, S b){
    return a.y<b.y;
}
int N;
vector<S> v, v1;
vector<int> v2;

int idx[MAX_N+1];
int mn[MAX_N+1];
int two=1;

void update(int x, int y)
{
    while(x>0)
    {
        seg[x]+=y;
        x/=2;
    }
}

int sum(int x, int y)
{
    int s=0;
    while(x<=y)
    {
        if(x==y)
        {
            s+=seg[x];
            return s;
        }
        if(x%2)
        {
            s+=seg[x];
            x++;
        }
        if(!(y%2))
        {
            s+=seg[y];
            y--;
        }
        x/=2;
        y/=2;
    }
    return s;
}

void update2(int x)
{
    while(x>0)
    {
        chk[x]=1;
        x/=2;
    }
}

bool sum2(int x, int y)
{
    bool s=0;
    while(x<=y)
    {
        if(x==y)
        {
            s=(s|chk[x]);
            return s;
        }
        if(x%2)
        {
            s=(s|chk[x]);
            x++;
        }
        if(!(y%2))
        {
            s=(s|chk[y]);
            y--;
        }
        x/=2;
        y/=2;
    }
    return s;
}

int find_idx(int x)
{
    int tmp=x;
    int st=x;
    int fn=two+N;
    while(st<fn)
    {
        if(st==fn-1)
        {
            if(sum2(tmp, st))
            {
                return st;
            }
            return fn;
        }
        int mid=(st+fn)/2;
        if(sum2(tmp, mid))
        {
            fn=mid;
        }
        else
        {
            st=mid;
        }
    }
    return st;
}

long long ans;

int idx2[MAX_N+1];


int main()
{
    scanf("%d", &N);
    while(two<=(N+1))   two*=2;
    for(int i=1; i<=N; i++)
    {
        S scan;
        scanf("%d%d", &scan.x, &scan.y);
        v1.push_back(scan);
    }
    sort(v1.begin(), v1.end(), sf2);
    for(int i=0; i<N; i++)
    {
        v.push_back({v1[i].x, i});
    }
    v.push_back({-1, N});
    sort(v.begin(), v.end(), sf1);
    for(int i=0; i<=N; i++)
    {
        idx2[v[i].y]=i;
    }
    v1.clear();
    update2(two+N);
    for(int i=1; i<=N; i++)
    {
        idx[i]=find_idx(two+v[i].y+1)-two;
        update2(two+v[i].y);
        v1.push_back({idx2[idx[i]], i});
    }
    sort(v1.begin(), v1.end(), sf1);
    int ii=0;
    while(v1[ii].x==0)
    {
        ii++;
    }
    for(int i=1; i<=N; i++)
    {
        while(v1[ii].x==i)
        {
            mn[v1[ii].y]=sum(two, two+v[v1[ii].y].y);
            ii++;
        }
        int t=sum(two, two+v[i].y);
        ans+=(long long)t;
        update(two+v[i].y, 1-t);
        update(two+idx[i], mn[i]);
    }
    cout<<ans;
    return 0;
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &scan.x, &scan.y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 936 KB Output is correct
2 Incorrect 10 ms 936 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 366 ms 10764 KB Output is correct
2 Incorrect 487 ms 14620 KB Output isn't correct
3 Halted 0 ms 0 KB -