Submission #292556

#	Time	Username	Problem	Language	Result	Execution time	Memory
292556		davooddkareshki	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	618 ms	54352 KiB

fortune_telling2

// be name khoda
#include<bits/stdc++.h>

using namespace std;

#define F first
#define S second
//#define mp make_pair 
typedef long long ll;
#pragma GCC optimize("Ofast")

const int maxn = 2e5+10;
//const int mod = 1e9+7;
//const ll inf = 1e9+10;

int seg[maxn*20], L[maxn*20], R[maxn*20], n;
int root[maxn], lst;

void up(int v, int nw, int pos, int tl = 1, int tr = n)
{
    seg[nw] = seg[v] + 1;
    if(tl == tr) return;

    int tm = (tl + tr) >> 1;
    if(pos <= tm)
    {
        L[nw] = ++lst; R[nw] = R[v];
        up(L[v], L[nw], pos, tl, tm);
    }
    else
    {
        R[nw] = ++lst; L[nw] = L[v];
        up(R[v], R[nw], pos, tm+1, tr);
    }
}

int qu(int v, int l, int r, int tl = 1, int tr = n)
{
    if(l > r) return 0;
    if(tl == l && tr == r) return seg[v];
    
    int tm = (tl + tr) >> 1;
    return qu(L[v], l, min(tm,r), tl, tm) +
            qu(R[v], max(tm+1,l), r, tm+1, tr);
}

int qu2(int v1, int v2, int tl = 1, int tr = n)
{
    if(tl == tr) 
    {
        if(seg[v1] == seg[v2]) return tl;
        else return tl+1;
    }
    int tm = (tl + tr) >> 1;
    if(seg[R[v1]] == seg[R[v2]]) 
        return qu2(L[v1], L[v2], tl, tm);
    else
        return qu2(R[v1], R[v2], tm+1, tr);
}

vector<pair<int,int>> ve;
int QU(int x, int l, int r)
{
    int X = lower_bound(ve.begin(), ve.end(), make_pair(x,0)) - ve.begin();
    return qu(root[X], l, r);
}

int A[maxn], B[maxn];
signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int m; scanf("%d%d", &m, &n);
    for(int i = 1; i <= m; i++) scanf("%d%d", A+i, B+i);
    for(int i = 1, t; i <= n; i++)
    {scanf("%d", &t); ve.push_back({t,i});}
    
    sort(ve.begin(), ve.end());
    for(int i = ve.size()-1; i >= 0; i--)
    {
        int pos = ve[i].S;
        root[i] = ++lst;
        up(root[i+1], root[i], pos);
    }

    ll ans = 0;
    for(int i = 1, a, b; i <= m; i++)
    {
        a = A[i], b = B[i];
        int lo = 0, hi = n+1;
        int Xa = lower_bound(ve.begin(), ve.end(), make_pair(a,0)) - ve.begin();
        int Xb = lower_bound(ve.begin(), ve.end(), make_pair(b,0)) - ve.begin();

        hi = qu2(root[Xa], root[Xb]);

        int X = qu(root[Xa], hi, n);
        if(QU(min(a,b), 1, hi-1) == 0)
        {
            if(X&1) ans += b;
            else ans += a;
        }
        else
        {    
            if(X&1) ans += min(a,b); 
            else ans += max(a,b);
        }
    }
    printf("%lld", ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:90:13: warning: unused variable 'lo' [-Wunused-variable]
   90 |         int lo = 0, hi = n+1;
      |             ^~
fortune_telling2.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     int m; scanf("%d%d", &m, &n);
      |            ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:74:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     for(int i = 1; i <= m; i++) scanf("%d%d", A+i, B+i);
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:76:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |     {scanf("%d", &t); ve.push_back({t,i});}
      |      ~~~~~^~~~~~~~~~

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