oj.uz

답안 #364523

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364523 2021-02-09T12:03:36 Z daniel920712 운세 보기 2 (JOI14_fortune_telling2) C++14
35 / 100
 3000 ms 244356 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 < 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[2400005];
struct B
{
    int l,r;
    int nxl,nxr;
    int con;
}Node2[2400005];
int now=1,now2=1;
int Find(int x,int y,int here)
{
    int t=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;
    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) add2(where,Node2[here].nxl);
    else 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) add(l1,r1,l2,r2,con,Node[here].nxl);
    else if(l1>(Node[here].l+Node[here].r)/2) add(l1,r1,l2,r2,con,Node[here].nxr);
    else
    {
        add(l1,(Node[here].l+Node[here].r)/2,l2,r2,con,Node[here].nxl);
        add((Node[here].l+Node[here].r)/2+1,r1,l2,r2,con,Node[here].nxr);

    }
}
void BFS(int here)
{

    sort(Node[here].all.begin(),Node[here].all.end());
    if(Node[here].l==Node[here].r) return ;
    BFS(Node[here].nxl);
    BFS(Node[here].nxr);
}
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].add=0;
    if(l==r) return;
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
}
void build2(int l,int r,int here)
{
    Node2[here].l=l;
    Node2[here].r=r;
    Node2[here].con=0;
    if(l==r) return;
    Node2[here].nxl=now2++;
    Node2[here].nxr=now2++;
    build2(l,(l+r)/2,Node2[here].nxl);
    build2((l+r)/2+1,r,Node2[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(1e9+6);
    have.insert(0);
    have.insert(1);


    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;
    }

    build(0,have.size(),0);
    build2(0,have.size(),0);
    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+5],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(con%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

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 'void add(int, int, int, int, int, int)':
fortune_telling2.cpp:71:9: warning: unused variable 't' [-Wunused-variable]
   71 |     int t;
      |         ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:119:15: warning: unused variable 'j' [-Wunused-variable]
  119 |     int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
      |               ^
fortune_telling2.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |         scanf("%d %d",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:136:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  136 |         scanf("%d",&all[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 113644 KB Output is correct
2 Correct 75 ms 113704 KB Output is correct
3 Correct 88 ms 113900 KB Output is correct
4 Correct 79 ms 113900 KB Output is correct
5 Correct 75 ms 113856 KB Output is correct
6 Correct 76 ms 113900 KB Output is correct
7 Correct 78 ms 113900 KB Output is correct
8 Correct 80 ms 113880 KB Output is correct
9 Correct 75 ms 113900 KB Output is correct
10 Correct 72 ms 113388 KB Output is correct
11 Correct 75 ms 113772 KB Output is correct
12 Correct 74 ms 113772 KB Output is correct
13 Correct 75 ms 113772 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 113644 KB Output is correct
2 Correct 75 ms 113704 KB Output is correct
3 Correct 88 ms 113900 KB Output is correct
4 Correct 79 ms 113900 KB Output is correct
5 Correct 75 ms 113856 KB Output is correct
6 Correct 76 ms 113900 KB Output is correct
7 Correct 78 ms 113900 KB Output is correct
8 Correct 80 ms 113880 KB Output is correct
9 Correct 75 ms 113900 KB Output is correct
10 Correct 72 ms 113388 KB Output is correct
11 Correct 75 ms 113772 KB Output is correct
12 Correct 74 ms 113772 KB Output is correct
13 Correct 75 ms 113772 KB Output is correct
14 Correct 176 ms 121188 KB Output is correct
15 Correct 300 ms 129400 KB Output is correct
16 Correct 471 ms 137428 KB Output is correct
17 Correct 633 ms 145620 KB Output is correct
18 Correct 657 ms 145620 KB Output is correct
19 Correct 655 ms 145620 KB Output is correct
20 Correct 639 ms 145648 KB Output is correct
21 Correct 623 ms 145204 KB Output is correct
22 Correct 398 ms 131668 KB Output is correct
23 Correct 367 ms 128268 KB Output is correct
24 Correct 319 ms 125268 KB Output is correct
25 Correct 419 ms 134996 KB Output is correct
26 Correct 482 ms 138324 KB Output is correct
27 Correct 542 ms 139484 KB Output is correct
28 Correct 490 ms 139348 KB Output is correct
29 Correct 600 ms 142552 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 113644 KB Output is correct
2 Correct 75 ms 113704 KB Output is correct
3 Correct 88 ms 113900 KB Output is correct
4 Correct 79 ms 113900 KB Output is correct
5 Correct 75 ms 113856 KB Output is correct
6 Correct 76 ms 113900 KB Output is correct
7 Correct 78 ms 113900 KB Output is correct
8 Correct 80 ms 113880 KB Output is correct
9 Correct 75 ms 113900 KB Output is correct
10 Correct 72 ms 113388 KB Output is correct
11 Correct 75 ms 113772 KB Output is correct
12 Correct 74 ms 113772 KB Output is correct
13 Correct 75 ms 113772 KB Output is correct
14 Correct 176 ms 121188 KB Output is correct
15 Correct 300 ms 129400 KB Output is correct
16 Correct 471 ms 137428 KB Output is correct
17 Correct 633 ms 145620 KB Output is correct
18 Correct 657 ms 145620 KB Output is correct
19 Correct 655 ms 145620 KB Output is correct
20 Correct 639 ms 145648 KB Output is correct
21 Correct 623 ms 145204 KB Output is correct
22 Correct 398 ms 131668 KB Output is correct
23 Correct 367 ms 128268 KB Output is correct
24 Correct 319 ms 125268 KB Output is correct
25 Correct 419 ms 134996 KB Output is correct
26 Correct 482 ms 138324 KB Output is correct
27 Correct 542 ms 139484 KB Output is correct
28 Correct 490 ms 139348 KB Output is correct
29 Correct 600 ms 142552 KB Output is correct
30 Correct 2463 ms 216232 KB Output is correct
31 Correct 2781 ms 228256 KB Output is correct
32 Execution timed out 3095 ms 244356 KB Time limit exceeded
33 Halted 0 ms 0 KB -