oj.uz

Submission #364603

# Submission time Handle Problem Language Result Execution time Memory
364603 2021-02-09T13:53:18 Z daniel920712 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 2041 ms 154888 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;
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 < pair < int ,int > , int > all2;
map < int , pair < pair < vector < pair < pair < int ,int > , int > > , vector < pair < pair < int ,int > , int > > > , vector < pair < int , pair < int , int > > > > > query;
struct B
{
    int l,r;
    int nxl,nxr;
    int con;
}Node2[200005*35];
int now=1,now2=1;
 
void New2(int l,int r,int here)
{
    Node2[here].l=l;
    Node2[here].r=r;
    Node2[here].con=0;
    Node2[here].nxl=-1;
    Node2[here].nxr=-1;
}
int Find(int y,int here)
{
    int t=0;
    if(here==-1) return 0;
    if(all2.upper_bound((make_pair(y+1,(int) -1)))==all2.begin()) t=0;
    else
    {
 
        auto a=*prev(all2.upper_bound(make_pair(y+1,(int) -1)));
        if(a.first.first<=y&&a.first.second>=y) t+=a.second;
    }
    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)
{
    query[l1].first.first.push_back(make_pair(make_pair(l2,r2),con));
    query[r1+1].first.second.push_back(make_pair(make_pair(l2,r2),con));
}
int main()
{
    int N,K,i,j,con,ok=0,con2=0,tt,tt2;
    long long ans=0;
    scanf("%d %d",&N,&K);
    New2(0,1e9+5,0);
    for(i=0;i<N;i++)
    {
        scanf("%d %d",&x[i],&y[i]);
        query[x[i]].second.push_back(make_pair(y[i],make_pair(x[i],y[i])));
    }
    for(i=1;i<=K;i++)
    {
        scanf("%d",&all[i].first);
        all[i].second=i;
    }
    vis.insert(0);
    vis.insert(1e9+5);
 
    for(i=K;i>=1;i--)
    {
        con=0;
        con2=0;
        con=Find2(all[i].first+1,1e9+1,0);
        //for(j=i+1;j<=K;j++) if(all[j].first>all[i].first) con2++;
 
        if(vis.find(all[i].first)!=vis.end())
        {
            add2(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(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);
        add2(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(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);
 
 
 
    for(auto i:query)
    {
        for(auto j:i.second.first.second) all2.erase(j.first);
        for(auto j:i.second.first.first) all2[j.first]=j.second;
        for(auto j:i.second.second)
        {
            if(Find(j.first,0)==1) ans+=j.second.first;
            else ans+=j.second.second;
        }
 
    }
    printf("%lld\n",ans);
 
    return 0;
}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1132 KB Output is correct
2 Correct 4 ms 1160 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 5 ms 1260 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 5 ms 1260 KB Output is correct
7 Correct 5 ms 1260 KB Output is correct
8 Correct 5 ms 1260 KB Output is correct
9 Correct 4 ms 1260 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 4 ms 1260 KB Output is correct
12 Correct 4 ms 1260 KB Output is correct
13 Correct 4 ms 1260 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1132 KB Output is correct
2 Correct 4 ms 1160 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 5 ms 1260 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 5 ms 1260 KB Output is correct
7 Correct 5 ms 1260 KB Output is correct
8 Correct 5 ms 1260 KB Output is correct
9 Correct 4 ms 1260 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 4 ms 1260 KB Output is correct
12 Correct 4 ms 1260 KB Output is correct
13 Correct 4 ms 1260 KB Output is correct
14 Correct 61 ms 8932 KB Output is correct
15 Correct 134 ms 17116 KB Output is correct
16 Correct 212 ms 25172 KB Output is correct
17 Correct 306 ms 33056 KB Output is correct
18 Correct 304 ms 33148 KB Output is correct
19 Correct 303 ms 32980 KB Output is correct
20 Correct 287 ms 32980 KB Output is correct
21 Correct 272 ms 32980 KB Output is correct
22 Correct 187 ms 17620 KB Output is correct
23 Correct 176 ms 16340 KB Output is correct
24 Correct 164 ms 14420 KB Output is correct
25 Correct 203 ms 19540 KB Output is correct
26 Correct 235 ms 29524 KB Output is correct
27 Correct 233 ms 30164 KB Output is correct
28 Correct 224 ms 29908 KB Output is correct
29 Correct 285 ms 32084 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1132 KB Output is correct
2 Correct 4 ms 1160 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 5 ms 1260 KB Output is correct
5 Correct 7 ms 1260 KB Output is correct
6 Correct 5 ms 1260 KB Output is correct
7 Correct 5 ms 1260 KB Output is correct
8 Correct 5 ms 1260 KB Output is correct
9 Correct 4 ms 1260 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 4 ms 1260 KB Output is correct
12 Correct 4 ms 1260 KB Output is correct
13 Correct 4 ms 1260 KB Output is correct
14 Correct 61 ms 8932 KB Output is correct
15 Correct 134 ms 17116 KB Output is correct
16 Correct 212 ms 25172 KB Output is correct
17 Correct 306 ms 33056 KB Output is correct
18 Correct 304 ms 33148 KB Output is correct
19 Correct 303 ms 32980 KB Output is correct
20 Correct 287 ms 32980 KB Output is correct
21 Correct 272 ms 32980 KB Output is correct
22 Correct 187 ms 17620 KB Output is correct
23 Correct 176 ms 16340 KB Output is correct
24 Correct 164 ms 14420 KB Output is correct
25 Correct 203 ms 19540 KB Output is correct
26 Correct 235 ms 29524 KB Output is correct
27 Correct 233 ms 30164 KB Output is correct
28 Correct 224 ms 29908 KB Output is correct
29 Correct 285 ms 32084 KB Output is correct
30 Correct 1448 ms 123408 KB Output is correct
31 Correct 1588 ms 130084 KB Output is correct
32 Correct 1736 ms 138332 KB Output is correct
33 Correct 2001 ms 154888 KB Output is correct
34 Correct 1431 ms 121636 KB Output is correct
35 Correct 2021 ms 154776 KB Output is correct
36 Correct 1999 ms 154664 KB Output is correct
37 Correct 2004 ms 154796 KB Output is correct
38 Correct 2041 ms 154752 KB Output is correct
39 Correct 1999 ms 154664 KB Output is correct
40 Correct 1846 ms 154744 KB Output is correct
41 Correct 2013 ms 154828 KB Output is correct
42 Correct 2011 ms 154764 KB Output is correct
43 Correct 1610 ms 153328 KB Output is correct
44 Correct 1604 ms 150812 KB Output is correct
45 Correct 1616 ms 145552 KB Output is correct
46 Correct 1239 ms 79292 KB Output is correct
47 Correct 1103 ms 67400 KB Output is correct
48 Correct 1649 ms 139940 KB Output is correct
49 Correct 1567 ms 138512 KB Output is correct