oj.uz

답안 #364413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364413 2021-02-09T05:42:26 Z daniel920712 운세 보기 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 165776 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

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 101228 KB Output is correct
2 Correct 67 ms 101228 KB Output is correct
3 Correct 67 ms 101228 KB Output is correct
4 Correct 65 ms 101228 KB Output is correct
5 Correct 64 ms 101228 KB Output is correct
6 Correct 64 ms 101228 KB Output is correct
7 Correct 68 ms 101228 KB Output is correct
8 Correct 65 ms 101228 KB Output is correct
9 Correct 65 ms 101228 KB Output is correct
10 Correct 57 ms 99308 KB Output is correct
11 Correct 65 ms 101240 KB Output is correct
12 Correct 65 ms 101228 KB Output is correct
13 Correct 67 ms 101228 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 101228 KB Output is correct
2 Correct 67 ms 101228 KB Output is correct
3 Correct 67 ms 101228 KB Output is correct
4 Correct 65 ms 101228 KB Output is correct
5 Correct 64 ms 101228 KB Output is correct
6 Correct 64 ms 101228 KB Output is correct
7 Correct 68 ms 101228 KB Output is correct
8 Correct 65 ms 101228 KB Output is correct
9 Correct 65 ms 101228 KB Output is correct
10 Correct 57 ms 99308 KB Output is correct
11 Correct 65 ms 101240 KB Output is correct
12 Correct 65 ms 101228 KB Output is correct
13 Correct 67 ms 101228 KB Output is correct
14 Correct 231 ms 117664 KB Output is correct
15 Correct 476 ms 134360 KB Output is correct
16 Correct 824 ms 150124 KB Output is correct
17 Correct 1261 ms 165648 KB Output is correct
18 Correct 1294 ms 165776 KB Output is correct
19 Correct 1311 ms 165744 KB Output is correct
20 Correct 1247 ms 165456 KB Output is correct
21 Correct 1273 ms 165568 KB Output is correct
22 Correct 855 ms 112340 KB Output is correct
23 Correct 839 ms 110936 KB Output is correct
24 Correct 817 ms 109604 KB Output is correct
25 Correct 868 ms 114320 KB Output is correct
26 Correct 1193 ms 164940 KB Output is correct
27 Correct 1275 ms 165472 KB Output is correct
28 Correct 1260 ms 163232 KB Output is correct
29 Correct 1349 ms 165516 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 101228 KB Output is correct
2 Correct 67 ms 101228 KB Output is correct
3 Correct 67 ms 101228 KB Output is correct
4 Correct 65 ms 101228 KB Output is correct
5 Correct 64 ms 101228 KB Output is correct
6 Correct 64 ms 101228 KB Output is correct
7 Correct 68 ms 101228 KB Output is correct
8 Correct 65 ms 101228 KB Output is correct
9 Correct 65 ms 101228 KB Output is correct
10 Correct 57 ms 99308 KB Output is correct
11 Correct 65 ms 101240 KB Output is correct
12 Correct 65 ms 101228 KB Output is correct
13 Correct 67 ms 101228 KB Output is correct
14 Correct 231 ms 117664 KB Output is correct
15 Correct 476 ms 134360 KB Output is correct
16 Correct 824 ms 150124 KB Output is correct
17 Correct 1261 ms 165648 KB Output is correct
18 Correct 1294 ms 165776 KB Output is correct
19 Correct 1311 ms 165744 KB Output is correct
20 Correct 1247 ms 165456 KB Output is correct
21 Correct 1273 ms 165568 KB Output is correct
22 Correct 855 ms 112340 KB Output is correct
23 Correct 839 ms 110936 KB Output is correct
24 Correct 817 ms 109604 KB Output is correct
25 Correct 868 ms 114320 KB Output is correct
26 Correct 1193 ms 164940 KB Output is correct
27 Correct 1275 ms 165472 KB Output is correct
28 Correct 1260 ms 163232 KB Output is correct
29 Correct 1349 ms 165516 KB Output is correct
30 Execution timed out 3075 ms 111644 KB Time limit exceeded
31 Halted 0 ms 0 KB -