Submission #364510

#	Time	Username	Problem	Language	Result	Execution time	Memory
364510		daniel920712	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	54 ms	83052 KiB

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;
int x[200005],y[200005];
pair < int , int > all[200005];
vector < pair < pair < int , int > , pair < int , int > > > a,b;
bool F(pair < int , int > a,pair < int , int > b)
{
    if(a.first>b.first) return 1;
    if(a.first<b.first) return 0;
    return a.second<b.second;
}
set < int > vis;
map < int , int > cha;
set < int > have;
struct A
{
    int l,r;
    int nxl,nxr,nxt;
    int add;
    vector < pair < pair < int ,int > , int > > all;
}Node[50005*35+5];
struct B
{
    int l,r;
    int nxl,nxr;
    int con;
}Node2[1000005];
int now=1,now2=1;
void New(int l,int r,int a,int here)
{
    //if((l+r)<0) while(1);
    Node[here].l=l;
    Node[here].r=r;
    Node[here].add=0;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
    Node[here].nxt=a;
}
void New2(int l,int r,int here)
{
    //if((l+r)<0) while(1);
    Node2[here].l=l;
    Node2[here].r=r;
    Node2[here].con=0;
    Node2[here].nxl=-1;
    Node2[here].nxr=-1;
}
int Find(int x,int y,int here)
{
    int t=0;
    if(here==-1) return 0;
    if(upper_bound(Node[here].all.begin(),Node[here].all.end(),make_pair(make_pair(y+1,(int) -1),(int) -1))==Node[here].all.begin()) t=0;
    else
    {

        auto a=*prev(upper_bound(Node[here].all.begin(),Node[here].all.end(),make_pair(make_pair(y+1,(int) -1),(int) -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;
}
int Find2(int l,int r,int here)
{
    int t=0;
    if(here==-1) return 0;
    t=0;
    if(l==Node2[here].l&&r==Node2[here].r) return Node2[here].con;
    if(r<=(Node2[here].l+Node2[here].r)/2) return Find2(l,r,Node2[here].nxl);
    else if(l>(Node2[here].l+Node2[here].r)/2) return Find2(l,r,Node2[here].nxr);
    else return Find2(l,(Node2[here].l+Node2[here].r)/2,Node2[here].nxl)+Find2((Node2[here].l+Node2[here].r)/2+1,r,Node2[here].nxr);
}
void add2(int where,int here)
{
    Node2[here].con++;
    if(where==Node2[here].l&&where==Node2[here].r) return;
    if(where<=(Node2[here].l+Node2[here].r)/2)
    {
        if(Node2[here].nxl==-1)
        {
            Node2[here].nxl=now2++;
            New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,Node2[here].nxl);
        }
        add2(where,Node2[here].nxl);
    }
    else
    {
        if(Node2[here].nxr==-1)
        {
            Node2[here].nxr=now2++;
            New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,Node2[here].nxr);
        }
        add2(where,Node2[here].nxr);
    }

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

    if(l1==Node[here].l&&r1==Node[here].r)
    {
        Node[here].all.push_back(make_pair(make_pair(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(int here)
{
    if(here==-1) return ;
    sort(Node[here].all.begin(),Node[here].all.end());
    BFS(Node[here].nxl);
    BFS(Node[here].nxr);
}
int main()
{
    int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
    long long ans=0;
    scanf("%d %d",&N,&K);
    have.insert(1e9+5);
    have.insert(0);
    New(0,1e6+5,-1,0);
    New2(0,1e6+5,0);
    for(i=0;i<N;i++)
    {
        scanf("%d %d",&x[i],&y[i]);
        have.insert(x[i]);
        have.insert(y[i]);
    }
    for(i=1;i<=K;i++)
    {
        scanf("%d",&all[i].first);
        have.insert(all[i].first);
        have.insert(all[i].first+1);
        all[i].second=i;
    }
    vis.insert(0);
    vis.insert(1e9+5);

    for(auto i:have) cha[i]=ttt++;

    for(i=K;i>=1;i--)
    {
        con=0;
        con2=0;
        con=Find2(cha[all[i].first+1],cha[1e9+1],0);

        if(vis.find(all[i].first)!=vis.end())
        {
            add2(cha[all[i].first],0);
            continue;
        }
        //printf("%lld\n",all[j])
        //if(con!=con2) return 1;
        tt=*vis.upper_bound(all[i].first);
        tt2=*prev(vis.upper_bound(all[i].first));
        if(con2%2==0)
        {
            a.push_back(make_pair(make_pair(cha[all[i].first+1],cha[tt]),make_pair(cha[tt2+1],cha[all[i].first])));
            b.push_back(make_pair(make_pair(cha[tt2+1],cha[all[i].first]),make_pair(cha[all[i].first+1],cha[tt])));
        }
        else
        {
            b.push_back(make_pair(make_pair(cha[all[i].first+1],cha[tt]),make_pair(cha[tt2+1],cha[all[i].first])));
            a.push_back(make_pair(make_pair(cha[tt2+1],cha[all[i].first]),make_pair(cha[all[i].first+1],cha[tt])));
        }
        vis.insert(all[i].first);
        add2(cha[all[i].first],0);

    }

    all[0].first=1e9+5;
    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=i;

        if(all[i].first!=all[i-1].first)
        {
            if(con2%2==1) a.push_back(make_pair(make_pair(cha[all[i].first+1],cha[all[i-1].first]),make_pair(cha[all[i].first+1],cha[all[i-1].first])));
            else b.push_back(make_pair(make_pair(cha[all[i].first+1],cha[all[i-1].first]),make_pair(cha[all[i].first+1],cha[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(cha[x[i]],cha[y[i]],0);
        if(ok==1000000000) ans+=(long long)y[i];
        else if(ok==1) ans+=(long long)x[i];
        else while(1);
    }
    printf("%lld\n",ans);

    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int Find2(int, int, int)':
fortune_telling2.cpp:76:9: warning: variable 't' set but not used [-Wunused-but-set-variable]
   76 |     int t=0;
      |         ^
fortune_telling2.cpp: In function 'void add(int, int, int, int, int, int)':
fortune_telling2.cpp:110:9: warning: unused variable 't' [-Wunused-variable]
  110 |     int t;
      |         ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:161:15: warning: unused variable 'j' [-Wunused-variable]
  161 |     int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
      |               ^
fortune_telling2.cpp:161:17: warning: variable 'con' set but not used [-Wunused-but-set-variable]
  161 |     int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
      |                 ^~~
fortune_telling2.cpp:163:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:170:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  170 |         scanf("%d %d",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  176 |         scanf("%d",&all[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

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