oj.uz

Submission #21066

# Submission time Handle Problem Language Result Execution time Memory
21066 2017-04-04T09:33:22 Z sbansalcs Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 493 ms 43976 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 25460 KB Output is correct
2 Correct 0 ms 25460 KB Output is correct
3 Correct 0 ms 25632 KB Output is correct
4 Correct 0 ms 25632 KB Output is correct
5 Correct 0 ms 25632 KB Output is correct
6 Correct 3 ms 25632 KB Output is correct
7 Correct 0 ms 25632 KB Output is correct
8 Correct 0 ms 25632 KB Output is correct
9 Correct 0 ms 25632 KB Output is correct
10 Correct 0 ms 25632 KB Output is correct
11 Correct 0 ms 25632 KB Output is correct
12 Correct 0 ms 25632 KB Output is correct
13 Correct 0 ms 25632 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26120 KB Output is correct
2 Correct 36 ms 26696 KB Output is correct
3 Correct 59 ms 27848 KB Output is correct
4 Correct 79 ms 27848 KB Output is correct
5 Correct 83 ms 27848 KB Output is correct
6 Correct 86 ms 27848 KB Output is correct
7 Correct 73 ms 27848 KB Output is correct
8 Correct 73 ms 27848 KB Output is correct
9 Correct 53 ms 27848 KB Output is correct
10 Correct 46 ms 27848 KB Output is correct
11 Correct 56 ms 27848 KB Output is correct
12 Correct 56 ms 27848 KB Output is correct
13 Correct 69 ms 27848 KB Output is correct
14 Correct 69 ms 27848 KB Output is correct
15 Correct 69 ms 27848 KB Output is correct
16 Correct 63 ms 27848 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 30152 KB Output is correct
2 Correct 209 ms 34760 KB Output is correct
3 Correct 289 ms 34760 KB Output is correct
4 Correct 469 ms 43976 KB Output is correct
5 Correct 116 ms 30152 KB Output is correct
6 Correct 466 ms 43976 KB Output is correct
7 Correct 489 ms 43976 KB Output is correct
8 Correct 493 ms 43976 KB Output is correct
9 Correct 476 ms 43976 KB Output is correct
10 Correct 433 ms 43976 KB Output is correct
11 Correct 446 ms 43976 KB Output is correct
12 Correct 436 ms 43976 KB Output is correct
13 Correct 423 ms 43976 KB Output is correct
14 Correct 323 ms 43976 KB Output is correct
15 Correct 276 ms 43976 KB Output is correct
16 Correct 319 ms 43976 KB Output is correct
17 Correct 326 ms 43976 KB Output is correct
18 Correct 333 ms 43976 KB Output is correct
19 Correct 399 ms 43976 KB Output is correct
20 Correct 416 ms 43976 KB Output is correct