Submission #945277

#	Time	Username	Problem	Language	Result	Execution time	Memory
945277		tset	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	11 ms	41052 KiB

fortune_telling2

#include<bits/stdc++.h> 
using namespace std;

#define int long long

const int T = 1048576;
const int INF = 1e18;


vector<int > ab;
void upd(int nde)
{
    ab[nde] = max(ab[nde *2], ab[nde*2 +1]);
    if(nde > 1)
        upd(nde /2);
}

void setValue(int nde, int val)
{
    ab[nde+T] = val;
    upd((nde+T)/2);
}

int query(int nde, int RB, int RE, int GB, int GE)
{
    if(GB > RE || RB > GE)
        return -INF;
    if(RB >= GB && RE <=  GE)
        return ab[nde];
    int mid = (RB + RE)/2;
    return max(query(nde *2, RB, mid, GB, GE), query(nde*2 +1, mid+1, RE, GB, GE));
}

vector<int > ab2;

void upd2(int nde)
{
    ab2[nde] = ab2[nde *2] + ab2[nde*2 +1];
    if(nde > 1)
        upd(nde /2);
}

void addRange(int nde, int RB, int RE, int GB, int GE, int val)
{
    //printf("%lld %lld %lld %lld %lld %lld \n", nde, RB, RE, GB, GE, val);
    if(GB > RE || RB > GE)
        return;
    if(RB >= GB && RE <=  GE)
    {
        ab2[nde] += val;
        return;
    }
    int mid = (RB + RE)/2;
    addRange(nde *2, RB, mid, GB, GE, val);
    addRange(nde*2 +1, mid+1, RE, GB, GE, val);
}

int getValue(int pos)
{
    int ans = 0;
    pos += T;
    while (pos >= 1)
    {
        ans += ab2[pos];
        pos/=2;
    }
    return ans;
}

signed main()
{
    int N, K;
    scanf("%lld%lld", &N, &K);

    vector<pair<int, int>> data;
    vector<int > queries(K);
    vector<int> original(1000000);
    map<int, int> compressed;
    set<int> values;
    for(int iN = 0; iN < N; iN ++)
    {
        int Ai, Bi;
        scanf("%lld %lld", &Ai, &Bi);
        data.push_back({Ai, Bi});
        values.insert(Ai);
        values.insert(Bi);
    }
    for(int iQ = 0; iQ< K; iQ++)
    {
        int Ti;
        scanf("%lld", &Ti);
        queries[iQ] = Ti;
        values.insert(Ti);
    }
    int idAct = 1;
    for(int val : values)
    {
        compressed[val] = idAct;
        original[idAct] = val; 
        idAct++; 
    }
    vector<int> rotaInit(N, 0);
    vector<pair<int, int>> inters;
    vector<pair<int, int> > whenStop;
    vector<pair<int, int>> cards(N);
    vector<int> ans(N, -INF);

    ab.assign(2*T, -INF); ab2.assign(2*T, 0);
    for(int iK = 0; iK<K; iK++)
    {
        queries[iK] = compressed[queries[iK]];
        setValue(queries[iK], iK);
    }
    for(int iN = 0; iN< N; iN++)
    {
        int deb = compressed[data[iN].first];
        int fin = compressed[data[iN].second];
        if(deb > fin)
        {
            swap(deb, fin);
            rotaInit[iN]++;
        }
        cards[iN] = {deb, fin};
        int lastMX = query(1, 0, T-1, deb, fin-1);
        if(lastMX!=-INF)
        {
            //printf("card %lld : last end = query nu. %lld\n", iN, lastMX);
            whenStop.push_back({lastMX, iN});
        }

    }

    sort(whenStop.begin(), whenStop.end(), greater<pair<int, int>>());
    int posiWS = 0;
    for(int iQ = K-1; iQ >= 0; iQ--)
    {
        while (posiWS< whenStop.size() && whenStop[posiWS].first == iQ)
        {
            int iN = whenStop[posiWS].second;
            ans[iN]=getValue(compressed[max(cards[iN].first, cards[iN].second)])+1;//+1 bc on commence au max instant
            //printf("ans[%lld]=%lld\n", iN, ans[iN]);
            posiWS++;
        }
        addRange(1, 0, T-1, 0, queries[iQ], 1);
    }

    int ansTot = 0;
    for(int iN=0; iN<N; iN++)
    {
        if(ans[iN]==-INF)
        {
            ans[iN] = rotaInit[iN] + getValue(compressed[max(data[iN].first, data[iN].second)]);
        }
        //printf("%lld:%lld | %lld/%lld\n", iN, ans[iN],  original[cards[iN].first],  original[cards[iN].second]);
        if(ans[iN]%2 == 0)
            ansTot += original[cards[iN].first];
        else
            ansTot += original[cards[iN].second];
    }
    printf("%lld\n", ansTot);

    
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:137:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         while (posiWS< whenStop.size() && whenStop[posiWS].first == iQ)
      |                ~~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%lld%lld", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%lld %lld", &Ai, &Bi);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%lld", &Ti);
      |         ~~~~~^~~~~~~~~~~~~

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