제출 #225820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
225820		MKopchev	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1197 ms	52492 KiB

fortune_telling2

#include<bits/stdc++.h>
using namespace std;

const int nmax=2e5+42,inf=1e9+42;

int n,q;

pair<int,int> inp[nmax];

int changes[nmax];

vector<int> tree[4*nmax];

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].push_back(changes[l]);
        return;
    }
    int av=(l+r)/2;
    build(node*2,l,av);
    build(node*2+1,av+1,r);

    tree[node]=tree[node*2];
    for(auto w:tree[node*2+1])tree[node].push_back(w);

    sort(tree[node].begin(),tree[node].end());
}

int last_special[nmax];

int cnt(int node,int lower)
{
    int pos=lower_bound(tree[node].begin(),tree[node].end(),lower)-tree[node].begin();
    return tree[node].size()-pos;
}
int query(int node,int l,int r,int lq,int rq,int lower,int upper)
{
    if(l==lq&&r==rq)
    {
        return cnt(node,lower)-cnt(node,upper+1);
    }
    int av=(l+r)/2,ret=0;

    if(lq<=av)ret=ret+query(node*2,l,av,lq,min(av,rq),lower,upper);
    if(av<rq)ret=ret+query(node*2+1,av+1,r,max(av+1,lq),rq,lower,upper);
    return ret;
}
int main()
{
    scanf("%i%i",&n,&q);

    for(int i=1;i<=n;i++)
        scanf("%i%i",&inp[i].first,&inp[i].second);

    for(int i=1;i<=q;i++)scanf("%i",&changes[i]);

    build(1,1,q);

    for(int i=1;i<=n;i++)
    {
        int ok=0,not_ok=q+1;

        int mini=min(inp[i].first,inp[i].second);
        int maxi=max(inp[i].first,inp[i].second);

        while(not_ok-ok>1)
        {
            int av=(ok+not_ok)/2;
            if(query(1,1,q,av,q,mini,maxi-1)>0)ok=av;
            else not_ok=av;
        }

        last_special[i]=ok;
    }

    long long output=0;
    for(int i=1;i<=n;i++)
    {
        if(last_special[i]&&inp[i].first<inp[i].second)swap(inp[i].first,inp[i].second);

        int swaps=0;

        if(last_special[i]<q)swaps=query(1,1,q,last_special[i]+1,q,max(inp[i].first,inp[i].second),inf);

        if(swaps%2)swap(inp[i].first,inp[i].second);

        output+=inp[i].first;
    }
    printf("%lld\n",output);
    return 0;
}

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

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&inp[i].first,&inp[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:57:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=q;i++)scanf("%i",&changes[i]);
                          ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65