Submission #21066

#	Time	Username	Problem	Language	Result	Execution time	Memory
21066		sbansalcs	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	493 ms	43976 KiB

fortune_telling2

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define mid (start+end)/2
const int N = 2e5+2;
const int M=N*12,N2=N*3;
typedef long long ll;
int A[N],B[N],arr[N],T[N];
int ans[N*2];
int TREE2[M];
int D[N],X[N],Y[N];
int bit[N2];
ll act[N2];
int G;
void update2(int idx, int start, int end, int x, int v)  {
    if(start==end)  TREE2[idx]=v;
    else if(x<=mid) update2(idx*2, start, mid, x, v);
    else    update2(idx*2+1, mid+1, end, x, v);
    TREE2[idx]=v;
}

int query2(int idx, int start, int end, int a, int b)    {
    if(b<a) return 0;
    if(start>=a && end<=b)  return TREE2[idx];
    else if(start>b || end<a)   return 0;
    else    return max(query2(idx*2, start, mid,a,b),query2(idx*2+1, mid+1, end,a,b));
}

void add(int i, int v)  {
    while (i<=N2) {
        bit[i]+=v;
        i+=(i&-i);
    }
}
int smquery(int i)  {
    int sum=0;
    while (i>0) {
        sum+=bit[i];
        i-=(i&-i);
    }
    return sum;
}





int main() {
    vector<pair<int, pair<int, int>>> vt;
    int n,k,x;scanf("%d %d",&n,&k);
    for (int i=1; i<=n; i++) {
        scanf("%d",&x);
        vt.push_back({x,{1,i}});
        scanf("%d",&x);
        vt.push_back({x,{2,i}});
    }
    for (int i=1; i<=k; i++) {
        scanf("%d",&x);
        vt.push_back({x,{3,i}});
    }
    sort(vt.begin(),vt.end());
    int i=0,h,g=0;
    while (i<vt.size()) {
        
        h=vt[i].first;
        g++;
        act[g]=h;
        while (i<vt.size() && vt[i].first==h) {
            x=vt[i].second.second;
            if(vt[i].second.first==1)   {
                A[x]=g;
            }
            else if(vt[i].second.first==2)  {
                B[x]=g;
            }
            else    {
                T[x]=g;
            }
            i++;
        }
    }
    G=g;
    for (int i=1; i<=k; i++) {
        update2(1, 1, g, T[i], i);
    }
    vt.clear();
    int y,c,z;
    int f=0;
    for (int i=1; i<=n; i++) {
        x=min(A[i],B[i]);
        y=max(A[i],B[i]);
        c=query2(1, 1, g, x, y-1);
        if(c==0)    {
            D[i]=0;
            f++;
            X[i]=f;
            vt.push_back({k,{y,f}});
        }
        else    {
            D[i]=1;
            f++;
            X[i]=f;
            vt.push_back({k,{y,f}});
            f++;
            Y[i]=f;
            vt.push_back({c,{y,f}});
        }
    }
    
    int j=1;
    sort(vt.begin(),vt.end());
    
    for(auto qr:vt) {
        x=qr.first;
        y=qr.second.first;
        z=qr.second.second;
        while (j<=x) {
            add(T[j], 1);
            j++;
        }
        ans[z]=smquery(g)-smquery(y-1);
    }
    ll total=0;
    for (int i=1; i<=n; i++) {
        x=min(A[i],B[i]);
        y=max(A[i],B[i]);
        if(D[i]==0) {
            if(ans[X[i]]%2==0)  total+=act[A[i]];
            else    total+=act[B[i]];
        }
        else    {
            c=ans[X[i]]-ans[Y[i]];
            if(c%2==0)  total+=act[y];
            else    total+=act[x];
        }
    }
    cout<<total<<endl;
    
    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (i<vt.size()) {
             ^
fortune_telling2.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (i<vt.size() && vt[i].first==h) {
                 ^
fortune_telling2.cpp:51:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n,k,x;scanf("%d %d",&n,&k);
                                   ^
fortune_telling2.cpp:53:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
fortune_telling2.cpp:55:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^
fortune_telling2.cpp:59:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
                       ^

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65