oj.uz

Submission #547437

# Submission time Handle Problem Language Result Execution time Memory
547437 2022-04-10T17:27:07 Z krit3379 Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 3000 ms 202700 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 200005

class node{
public:
    node *l,*r;
    int cnt;
    node(int cnt):l(NULL),r(NULL),cnt(cnt){}
    node(node *l,node *r):l(l),r(r),cnt(0){
        if(l)cnt+=l->cnt;
        if(r)cnt+=r->cnt;
    }
};
using pnode = node*;

pnode root[N];

pnode cre(int l,int r){
    if(l==r)return new node(0);
    int mid=(l+r)/2;
    return new node(cre(l,mid),cre(mid+1,r));
}

pnode update(pnode x,int l,int r,int p){
    if(l==r)return new node(x->cnt+1);
    int mid=(l+r)/2;
    if(p<=mid)return new node(update(x->l,l,mid,p),x->r);
    else return new node(x->l,update(x->r,mid+1,r,p));
}

int sol(pnode x,int l,int r,int ll,int rr){
    if(l>rr||ll>r||ll>rr)return 0;
    if(ll<=l&&r<=rr)return x->cnt;
    int mid=(l+r)/2;
    return sol(x->l,l,mid,ll,rr)+sol(x->r,mid+1,r,ll,rr);
}

int a[N],b[N],t[N],sz;
long long ans;
map<int,int> mp;

int main(){
    int n,m,i,pmi,pma,pos,l,r,mid,cnt;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d %d",&a[i],&b[i]);
        mp[a[i]];
        mp[b[i]];
    }
    for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]];
    for(auto &[x,y]:mp)y=++sz;
    root[0]=cre(1,sz);
    for(i=1;i<=m;i++){
        root[i]=update(root[i-1],1,sz,mp[t[i]]);
    }
    for(i=1;i<=n;i++){
        //search for last t that mi <= t < ma
        auto [mi,ma]=minmax(a[i],b[i]);
        pmi=mp[mi];
        pma=mp[ma];
        pos=0;
        l=1,r=m;
        while(l<=r){
            mid=(l+r)/2;
            cnt=sol(root[m],1,sz,pmi,pma-1)-sol(root[mid-1],1,sz,pmi,pma-1);
            if(cnt)pos=mid,l=mid+1;
            else r=mid-1;
        }
        if(pos){
            cnt=sol(root[m],1,sz,pma,sz)-sol(root[pos],1,sz,pma,sz);
            ans+=(cnt%2)?mi:ma;
        }
        else{
            cnt=sol(root[m],1,sz,pma,sz);
            ans+=(cnt%2)?b[i]:a[i];
        }
    }
    printf("%lld",ans);
    return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d %d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:51:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]];
      |                      ~~~~~^~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 9 ms 1064 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 5 ms 1056 KB Output is correct
9 Correct 5 ms 1068 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 980 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 9 ms 1064 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 5 ms 1056 KB Output is correct
9 Correct 5 ms 1068 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 84 ms 9060 KB Output is correct
15 Correct 226 ms 18432 KB Output is correct
16 Correct 307 ms 28128 KB Output is correct
17 Correct 524 ms 37832 KB Output is correct
18 Correct 505 ms 37828 KB Output is correct
19 Correct 493 ms 37832 KB Output is correct
20 Correct 505 ms 37892 KB Output is correct
21 Correct 488 ms 37796 KB Output is correct
22 Correct 320 ms 32292 KB Output is correct
23 Correct 317 ms 29532 KB Output is correct
24 Correct 264 ms 27484 KB Output is correct
25 Correct 343 ms 33824 KB Output is correct
26 Correct 283 ms 31580 KB Output is correct
27 Correct 394 ms 32776 KB Output is correct
28 Correct 323 ms 32768 KB Output is correct
29 Correct 401 ms 35472 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 9 ms 1064 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 4 ms 980 KB Output is correct
8 Correct 5 ms 1056 KB Output is correct
9 Correct 5 ms 1068 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 4 ms 980 KB Output is correct
14 Correct 84 ms 9060 KB Output is correct
15 Correct 226 ms 18432 KB Output is correct
16 Correct 307 ms 28128 KB Output is correct
17 Correct 524 ms 37832 KB Output is correct
18 Correct 505 ms 37828 KB Output is correct
19 Correct 493 ms 37832 KB Output is correct
20 Correct 505 ms 37892 KB Output is correct
21 Correct 488 ms 37796 KB Output is correct
22 Correct 320 ms 32292 KB Output is correct
23 Correct 317 ms 29532 KB Output is correct
24 Correct 264 ms 27484 KB Output is correct
25 Correct 343 ms 33824 KB Output is correct
26 Correct 283 ms 31580 KB Output is correct
27 Correct 394 ms 32776 KB Output is correct
28 Correct 323 ms 32768 KB Output is correct
29 Correct 401 ms 35472 KB Output is correct
30 Correct 749 ms 146800 KB Output is correct
31 Correct 1346 ms 159308 KB Output is correct
32 Correct 2304 ms 174480 KB Output is correct
33 Execution timed out 3097 ms 202700 KB Time limit exceeded
34 Halted 0 ms 0 KB -