oj.uz

Submission #547434

# Submission time Handle Problem Language Result Execution time Memory
547434 2022-04-10T17:03:38 Z krit3379 Fortune Telling 2 (JOI14_fortune_telling2) C++17
0 / 100
 4 ms 800 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;
vector<int> v;
map<int,int> mp;

int main(){
    int n,m,i,mi,ma,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]);
    }
    for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]],v.push_back(t[i]);
    v.push_back(-1);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    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=lower_bound(v.begin(),v.end(),mi)-v.begin();
        pma=lower_bound(v.begin(),v.end(),ma)-v.begin();
        pos=0;
        l=1,r=sz;
        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:15: warning: unused variable 'mi' [-Wunused-variable]
   45 |     int n,m,i,mi,ma,pmi,pma,pos,l,r,mid,cnt;
      |               ^~
fortune_telling2.cpp:45:18: warning: unused variable 'ma' [-Wunused-variable]
   45 |     int n,m,i,mi,ma,pmi,pma,pos,l,r,mid,cnt;
      |                  ^~
fortune_telling2.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%d %d",&a[i],&b[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:50:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     for(i=1;i<=m;i++)scanf("%d",&t[i]),mp[t[i]],v.push_back(t[i]);
      |                      ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 4 ms 800 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Incorrect 3 ms 724 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 4 ms 800 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Incorrect 3 ms 724 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 4 ms 724 KB Output is correct
4 Correct 4 ms 800 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Incorrect 3 ms 724 KB Output isn't correct
11 Halted 0 ms 0 KB -