oj.uz

Submission #364411

# Submission time Handle Problem Language Result Execution time Memory
364411 2021-02-09T05:39:05 Z daniel920712 Fortune Telling 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 170804 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[205*205*35+5];
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
    {
        //printf("aa\n");
        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));
        //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

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:58:15: warning: unused variable 't' [-Wunused-variable]
   58 |     long long t;
      |               ^
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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 106220 KB Output is correct
2 Correct 67 ms 106220 KB Output is correct
3 Correct 69 ms 106220 KB Output is correct
4 Correct 69 ms 106240 KB Output is correct
5 Correct 68 ms 106348 KB Output is correct
6 Correct 70 ms 106220 KB Output is correct
7 Correct 69 ms 106252 KB Output is correct
8 Correct 69 ms 106220 KB Output is correct
9 Correct 68 ms 106220 KB Output is correct
10 Correct 59 ms 104172 KB Output is correct
11 Correct 70 ms 106220 KB Output is correct
12 Correct 69 ms 106220 KB Output is correct
13 Correct 78 ms 106220 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 106220 KB Output is correct
2 Correct 67 ms 106220 KB Output is correct
3 Correct 69 ms 106220 KB Output is correct
4 Correct 69 ms 106240 KB Output is correct
5 Correct 68 ms 106348 KB Output is correct
6 Correct 70 ms 106220 KB Output is correct
7 Correct 69 ms 106252 KB Output is correct
8 Correct 69 ms 106220 KB Output is correct
9 Correct 68 ms 106220 KB Output is correct
10 Correct 59 ms 104172 KB Output is correct
11 Correct 70 ms 106220 KB Output is correct
12 Correct 69 ms 106220 KB Output is correct
13 Correct 78 ms 106220 KB Output is correct
14 Correct 266 ms 122656 KB Output is correct
15 Correct 643 ms 139224 KB Output is correct
16 Correct 1182 ms 155216 KB Output is correct
17 Correct 1870 ms 170640 KB Output is correct
18 Correct 1860 ms 170644 KB Output is correct
19 Correct 1925 ms 170804 KB Output is correct
20 Correct 1892 ms 170704 KB Output is correct
21 Correct 1946 ms 170476 KB Output is correct
22 Correct 1511 ms 117472 KB Output is correct
23 Correct 1471 ms 116004 KB Output is correct
24 Correct 1428 ms 114440 KB Output is correct
25 Correct 1489 ms 119328 KB Output is correct
26 Correct 1866 ms 170144 KB Output is correct
27 Correct 1840 ms 170600 KB Output is correct
28 Correct 1830 ms 168332 KB Output is correct
29 Correct 1917 ms 170556 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 106220 KB Output is correct
2 Correct 67 ms 106220 KB Output is correct
3 Correct 69 ms 106220 KB Output is correct
4 Correct 69 ms 106240 KB Output is correct
5 Correct 68 ms 106348 KB Output is correct
6 Correct 70 ms 106220 KB Output is correct
7 Correct 69 ms 106252 KB Output is correct
8 Correct 69 ms 106220 KB Output is correct
9 Correct 68 ms 106220 KB Output is correct
10 Correct 59 ms 104172 KB Output is correct
11 Correct 70 ms 106220 KB Output is correct
12 Correct 69 ms 106220 KB Output is correct
13 Correct 78 ms 106220 KB Output is correct
14 Correct 266 ms 122656 KB Output is correct
15 Correct 643 ms 139224 KB Output is correct
16 Correct 1182 ms 155216 KB Output is correct
17 Correct 1870 ms 170640 KB Output is correct
18 Correct 1860 ms 170644 KB Output is correct
19 Correct 1925 ms 170804 KB Output is correct
20 Correct 1892 ms 170704 KB Output is correct
21 Correct 1946 ms 170476 KB Output is correct
22 Correct 1511 ms 117472 KB Output is correct
23 Correct 1471 ms 116004 KB Output is correct
24 Correct 1428 ms 114440 KB Output is correct
25 Correct 1489 ms 119328 KB Output is correct
26 Correct 1866 ms 170144 KB Output is correct
27 Correct 1840 ms 170600 KB Output is correct
28 Correct 1830 ms 168332 KB Output is correct
29 Correct 1917 ms 170556 KB Output is correct
30 Execution timed out 3066 ms 116704 KB Time limit exceeded
31 Halted 0 ms 0 KB -