답안 #364408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
364408	2021-02-09T05:33:36 Z	daniel920712	운세 보기 2 (JOI14_fortune_telling2)	C++14	컴파일 오류	0 ms	0 KB

fortune_telling2

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <map>
#include <vector>
#include <set>

using namespace std;
long long x[200005],y[200005];
pair < long long , long long > all[200005];
vector < pair < pair < long long , long long > , pair < long long , long long > > > a,b;
bool F(pair < long long , long long > a,pair < long long , long long > b)
{
    if(a.first>b.first) return 1;
    if(a.first<b.first) return 0;
    return a.second<b.second;
}
set < long long > vis;
struct A
{
    long long l,r;
    long long nxl,nxr,nxt;
    long long add;
    vector < pair < long long ,long long > , long long > all;
}Node[200005*20];
long long now=1;
void New(long long l,long long r,long long a,long long here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].add=0;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
    Node[here].nxt=a;
}
long long Find(long long x,long long y,long long here)
{
    long long t=0;
    if(here==-1) return 0;
    if(Node[here].all.empty()||Node[here].all.upper_bound(make_pair(y+1,-1))==Node[here].all.begin()) t=0;
    else
    {
        //printf("aa\n");
        auto a=*prev(Node[here].all.upper_bound(make_pair(y+1,-1)));
        if(a.first.first<=y&&a.first.second>=y) t+=a.second;
    }
    if(Node[here].l==Node[here].r) return t;
    if(x<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl);
    else t+=Find(x,y,Node[here].nxr);

    return t;
}
void add(long long l1,long long r1,long long l2,long long r2,long long con,long long here)
{
    long long t;

    if(l1==Node[here].l&&r1==Node[here].r)
    {
        Node[here].all[make_pair(l2,r2)]=con;
        //printf("%lld %lld %lld %lld %lld\n",l1,r1,l2,r2,con);
        return;
    }
    if(r1<=(Node[here].l+Node[here].r)/2)
    {
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            New(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
        }
        add(l1,r1,l2,r2,con,Node[here].nxl);
    }
    else if(l1>(Node[here].l+Node[here].r)/2)
    {
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            New((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr);
        }
        add(l1,r1,l2,r2,con,Node[here].nxr);
    }
    else
    {
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            New(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
        }
        add(l1,(Node[here].l+Node[here].r)/2,l2,r2,con,Node[here].nxl);
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            New((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr);
        }
        add((Node[here].l+Node[here].r)/2+1,r1,l2,r2,con,Node[here].nxr);

    }
}
void BFS(long long here)
{
    if(here==-1) return ;
    sort(Node[here].all.begin(),Node[here].all.end());
    BFS(Node[here].nxl);
    BFS(Node[here].nxr);
}
int main()
{
    long long N,K,i,j,con,ok=0,ans=0,con2=0,tt,tt2;
    scanf("%lld %lld",&N,&K);
    for(i=0;i<N;i++) scanf("%lld %lld",&x[i],&y[i]);
    for(i=1;i<=K;i++)
    {
        scanf("%lld",&all[i].first);
        all[i].second=i;
    }
    vis.insert(0);
    vis.insert(2e9);

    for(i=K;i>=1;i--)
    {
        con=0;
        for(j=i+1;j<=K;j++) if(all[j].first>all[i].first) con++;
        if(vis.find(all[i].first)!=vis.end()) continue;
        tt=*vis.upper_bound(all[i].first);
        tt2=*prev(vis.upper_bound(all[i].first));
        if(con%2==0)
        {
            a.push_back(make_pair(make_pair(all[i].first+1,tt),make_pair(tt2+1,all[i].first)));
            b.push_back(make_pair(make_pair(tt2+1,all[i].first),make_pair(all[i].first+1,tt)));
        }
        else
        {
            b.push_back(make_pair(make_pair(all[i].first+1,tt),make_pair(tt2+1,all[i].first)));
            a.push_back(make_pair(make_pair(tt2+1,all[i].first),make_pair(all[i].first+1,tt)));
        }
        vis.insert(all[i].first);
    }
    New(0,2e9,-1,0);
    all[0].first=2e9;
    all[0].second=0;
    sort(all+1,all+K+1,F);
    all[K+1].first=0;
    all[K+1].second=K+1;
    for(i=1;i<=K+1;i++)
    {
        con=0;
        con2=0;
        for(j=0;j<i;j++) if(all[j].second>all[i].second&&all[j].first>all[i].first) con++;
        for(j=0;j<i;j++) if(all[j].first>all[i].first) con2++;
        if(all[i].first!=all[i-1].first)
        {
            if(con2%2==1) a.push_back(make_pair(make_pair(all[i].first+1,all[i-1].first),make_pair(all[i].first+1,all[i-1].first)));
            else b.push_back(make_pair(make_pair(all[i].first+1,all[i-1].first),make_pair(all[i].first+1,all[i-1].first)));
        }
    }

    for(auto j:a) add(j.first.first,j.first.second,j.second.first,j.second.second,1,0);
    
    for(auto j:b) add(j.first.first,j.first.second,j.second.first,j.second.second,1e9,0);
    
    BFS(0);
    

    for(i=0;i<N;i++)
    {
        ok=0;
        ok=Find(x[i],y[i],0);
        if(ok==1000000000) ans+=y[i];
        else if(ok==1) ans+=x[i];
        else while(1);

    }
    printf("%lld\n",ans);

    return 0;
}

Compilation message

In file included from /usr/include/c++/9/vector:67,
                 from fortune_telling2.cpp:4:
/usr/include/c++/9/bits/stl_vector.h: In instantiation of 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>':
/usr/include/c++/9/bits/stl_vector.h:386:11:   required from 'class std::vector<std::pair<long long int, long long int>, long long int>'
fortune_telling2.cpp:27:58:   required from here
/usr/include/c++/9/bits/stl_vector.h:84:21: error: 'long long int' is not a class, struct, or union type
   84 |  rebind<_Tp>::other _Tp_alloc_type;
      |                     ^~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:86:9: error: 'long long int' is not a class, struct, or union type
   86 |         pointer;
      |         ^~~~~~~
/usr/include/c++/9/bits/stl_vector.h: In instantiation of 'class std::vector<std::pair<long long int, long long int>, long long int>':
fortune_telling2.cpp:27:58:   required from here
/usr/include/c++/9/bits/stl_vector.h:387:5: error: 'long long int' is not a class, struct, or union type
  387 |     {
      |     ^
/usr/include/c++/9/bits/stl_vector.h:471:20: error: no members matching 'std::vector<std::pair<long long int, long long int>, long long int>::_Base {aka std::_Vector_base<std::pair<long long int, long long int>, long long int>}::_M_allocate' in 'std::vector<std::pair<long long int, long long int>, long long int>::_Base' {aka 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>'}
  471 |       using _Base::_M_allocate;
      |                    ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:472:20: error: no members matching 'std::vector<std::pair<long long int, long long int>, long long int>::_Base {aka std::_Vector_base<std::pair<long long int, long long int>, long long int>}::_M_deallocate' in 'std::vector<std::pair<long long int, long long int>, long long int>::_Base' {aka 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>'}
  472 |       using _Base::_M_deallocate;
      |                    ^~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:474:20: error: no members matching 'std::vector<std::pair<long long int, long long int>, long long int>::_Base {aka std::_Vector_base<std::pair<long long int, long long int>, long long int>}::_M_get_Tp_allocator' in 'std::vector<std::pair<long long int, long long int>, long long int>::_Base' {aka 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>'}
  474 |       using _Base::_M_get_Tp_allocator;
      |                    ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::_Vector_impl::_Vector_impl() [with _Tp = std::pair<long long int, long long int>; _Alloc = long long int]':
fortune_telling2.cpp:28:16:   recursively required from 'std::vector<_Tp, _Alloc>::vector() [with _Tp = std::pair<long long int, long long int>; _Alloc = long long int]'
fortune_telling2.cpp:28:16:   required from here
/usr/include/c++/9/bits/stl_vector.h:128:2: error: 'long long int' is not a class, struct, or union type
  128 |  _Vector_impl() _GLIBCXX_NOEXCEPT_IF(
      |  ^~~~~~~~~~~~
fortune_telling2.cpp: In function 'long long int Find(long long int, long long int, long long int)':
fortune_telling2.cpp:43:47: error: 'class std::vector<std::pair<long long int, long long int>, long long int>' has no member named 'upper_bound'
   43 |     if(Node[here].all.empty()||Node[here].all.upper_bound(make_pair(y+1,-1))==Node[here].all.begin()) t=0;
      |                                               ^~~~~~~~~~~
fortune_telling2.cpp:43:94: error: 'class std::vector<std::pair<long long int, long long int>, long long int>' has no member named 'begin'
   43 |     if(Node[here].all.empty()||Node[here].all.upper_bound(make_pair(y+1,-1))==Node[here].all.begin()) t=0;
      |                                                                                              ^~~~~
fortune_telling2.cpp:47:37: error: 'class std::vector<std::pair<long long int, long long int>, long long int>' has no member named 'upper_bound'
   47 |         auto a=*prev(Node[here].all.upper_bound(make_pair(y+1,-1)));
      |                                     ^~~~~~~~~~~
fortune_telling2.cpp: In function 'void add(long long int, long long int, long long int, long long int, long long int, long long int)':
fortune_telling2.cpp:62:23: error: no match for 'operator[]' (operand types are 'std::vector<std::pair<long long int, long long int>, long long int>' and 'std::pair<long long int, long long int>')
   62 |         Node[here].all[make_pair(l2,r2)]=con;
      |                       ^
fortune_telling2.cpp:58:15: warning: unused variable 't' [-Wunused-variable]
   58 |     long long t;
      |               ^
fortune_telling2.cpp: In function 'void BFS(long long int)':
fortune_telling2.cpp:104:25: error: 'class std::vector<std::pair<long long int, long long int>, long long int>' has no member named 'begin'
  104 |     sort(Node[here].all.begin(),Node[here].all.end());
      |                         ^~~~~
fortune_telling2.cpp:104:48: error: 'class std::vector<std::pair<long long int, long long int>, long long int>' has no member named 'end'
  104 |     sort(Node[here].all.begin(),Node[here].all.end());
      |                                                ^~~
In file included from /usr/include/c++/9/vector:67,
                 from fortune_telling2.cpp:4:
/usr/include/c++/9/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::_Vector_impl::_Vector_impl() [with _Tp = std::pair<long long int, long long int>; _Alloc = long long int]':
/usr/include/c++/9/bits/stl_vector.h:285:7:   required from here
/usr/include/c++/9/bits/stl_vector.h:130:19: error: 'long long int' is not a class, struct, or union type
  130 |  : _Tp_alloc_type()
      |                   ^
/usr/include/c++/9/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::pair<long long int, long long int>; _Alloc = long long int]':
/usr/include/c++/9/bits/stl_vector.h:484:7:   required from here
/usr/include/c++/9/bits/stl_vector.h:332:24: error: 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>::_Vector_impl' has no member named '_M_start'
  332 |  _M_deallocate(_M_impl._M_start,
      |                ~~~~~~~~^~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:333:17: error: 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>::_Vector_impl' has no member named '_M_end_of_storage'
  333 |         _M_impl._M_end_of_storage - _M_impl._M_start);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:333:45: error: 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>::_Vector_impl' has no member named '_M_start'
  333 |         _M_impl._M_end_of_storage - _M_impl._M_start);
      |                                     ~~~~~~~~^~~~~~~~
/usr/include/c++/9/bits/stl_vector.h: In instantiation of 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::pair<long long int, long long int>; _Alloc = long long int]':
fortune_telling2.cpp:22:8:   required from here
/usr/include/c++/9/bits/stl_vector.h:677:30: error: 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>::_Vector_impl' has no member named '_M_start'
  677 |  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
      |                ~~~~~~~~~~~~~~^~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:677:54: error: 'struct std::_Vector_base<std::pair<long long int, long long int>, long long int>::_Vector_impl' has no member named '_M_finish'
  677 |  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
      |                                        ~~~~~~~~~~~~~~^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:678:28: error: '_M_get_Tp_allocator' was not declared in this scope; did you mean 'get_allocator'?
  678 |         _M_get_Tp_allocator());
      |         ~~~~~~~~~~~~~~~~~~~^~
      |         get_allocator
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |     scanf("%lld %lld",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:112:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |     for(i=0;i<N;i++) scanf("%lld %lld",&x[i],&y[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |         scanf("%lld",&all[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~