oj.uz

Submission #364414

# Submission time Handle Problem Language Result Execution time Memory
364414 2021-02-09T05:42:45 Z daniel920712 Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 165756 KB 
#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 < pair < long long ,long long > , long long > > all;
}Node[40005*35+5];
struct B
{
    long long l,r;
    long long nxl,nxr;
    long long con;

}Node2[1000005];
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(upper_bound(Node[here].all.begin(),Node[here].all.end(),make_pair(make_pair(y+1,(long long) -1),(long long) -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,(long long) -1),(long long) -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.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(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=i;


        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

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:65:15: warning: unused variable 't' [-Wunused-variable]
   65 |     long long t;
      |               ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |     scanf("%lld %lld",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:118:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |     for(i=0;i<N;i++) scanf("%lld %lld",&x[i],&y[i]);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |         scanf("%lld",&all[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 101228 KB Output is correct
2 Correct 64 ms 101228 KB Output is correct
3 Correct 64 ms 101228 KB Output is correct
4 Correct 67 ms 101228 KB Output is correct
5 Correct 90 ms 101360 KB Output is correct
6 Correct 70 ms 101200 KB Output is correct
7 Correct 63 ms 101228 KB Output is correct
8 Correct 63 ms 101228 KB Output is correct
9 Correct 64 ms 101248 KB Output is correct
10 Correct 55 ms 99308 KB Output is correct
11 Correct 70 ms 101228 KB Output is correct
12 Correct 97 ms 101228 KB Output is correct
13 Correct 66 ms 101228 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 101228 KB Output is correct
2 Correct 64 ms 101228 KB Output is correct
3 Correct 64 ms 101228 KB Output is correct
4 Correct 67 ms 101228 KB Output is correct
5 Correct 90 ms 101360 KB Output is correct
6 Correct 70 ms 101200 KB Output is correct
7 Correct 63 ms 101228 KB Output is correct
8 Correct 63 ms 101228 KB Output is correct
9 Correct 64 ms 101248 KB Output is correct
10 Correct 55 ms 99308 KB Output is correct
11 Correct 70 ms 101228 KB Output is correct
12 Correct 97 ms 101228 KB Output is correct
13 Correct 66 ms 101228 KB Output is correct
14 Correct 250 ms 117704 KB Output is correct
15 Correct 496 ms 134504 KB Output is correct
16 Correct 847 ms 150096 KB Output is correct
17 Correct 1274 ms 165648 KB Output is correct
18 Correct 1284 ms 165756 KB Output is correct
19 Correct 1302 ms 165752 KB Output is correct
20 Correct 1272 ms 165696 KB Output is correct
21 Correct 1283 ms 165520 KB Output is correct
22 Correct 842 ms 112208 KB Output is correct
23 Correct 846 ms 110956 KB Output is correct
24 Correct 824 ms 109356 KB Output is correct
25 Correct 885 ms 114192 KB Output is correct
26 Correct 1224 ms 164820 KB Output is correct
27 Correct 1248 ms 165648 KB Output is correct
28 Correct 1198 ms 163360 KB Output is correct
29 Correct 1300 ms 165704 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 101228 KB Output is correct
2 Correct 64 ms 101228 KB Output is correct
3 Correct 64 ms 101228 KB Output is correct
4 Correct 67 ms 101228 KB Output is correct
5 Correct 90 ms 101360 KB Output is correct
6 Correct 70 ms 101200 KB Output is correct
7 Correct 63 ms 101228 KB Output is correct
8 Correct 63 ms 101228 KB Output is correct
9 Correct 64 ms 101248 KB Output is correct
10 Correct 55 ms 99308 KB Output is correct
11 Correct 70 ms 101228 KB Output is correct
12 Correct 97 ms 101228 KB Output is correct
13 Correct 66 ms 101228 KB Output is correct
14 Correct 250 ms 117704 KB Output is correct
15 Correct 496 ms 134504 KB Output is correct
16 Correct 847 ms 150096 KB Output is correct
17 Correct 1274 ms 165648 KB Output is correct
18 Correct 1284 ms 165756 KB Output is correct
19 Correct 1302 ms 165752 KB Output is correct
20 Correct 1272 ms 165696 KB Output is correct
21 Correct 1283 ms 165520 KB Output is correct
22 Correct 842 ms 112208 KB Output is correct
23 Correct 846 ms 110956 KB Output is correct
24 Correct 824 ms 109356 KB Output is correct
25 Correct 885 ms 114192 KB Output is correct
26 Correct 1224 ms 164820 KB Output is correct
27 Correct 1248 ms 165648 KB Output is correct
28 Correct 1198 ms 163360 KB Output is correct
29 Correct 1300 ms 165704 KB Output is correct
30 Execution timed out 3088 ms 111848 KB Time limit exceeded
31 Halted 0 ms 0 KB -