Submission #1113173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113173		lucascgar	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	195 ms	262144 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

/*
foco no cara da esquerda ativado ou nn

query so na esquerda: desligo
na direita: mudo
*/

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int MAXN = 5e4+10, MAXTT = 2*MAXN;

int s[MAXN], l[MAXN];

bitset<MAXN> r;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    int a, b;

    vector<pii> ord;

    for (int i=1;i<=n;i++){
        cin >> a >> b;
        s[i] = min(a,b), l[i] = max(a,b);
        if (a<b) r[i]=1;
        ord.emplace_back(l[i], i);
        ord.emplace_back(s[i], i);

    }

    sort(ord.begin(), ord.end());

    vector<bitset<MAXN>> es(ord.size()+1, bitset<MAXN>(0)), di(ord.size()+1, bitset<MAXN>(0));

    vector<int> count(ord.size());
    int cnt = 1;
    es[1].flip();
    for (int i=0;i<ord.size();i++){
        if (i>0 && ord[i].first != ord[i-1].first){
            cnt++;
            es[cnt] = es[cnt-1], di[cnt]=di[cnt-1];
        }
        count[i] = cnt;
        auto [v, x] = ord[i];

        if (v == s[x]){
            es[cnt][x] =0;
        }else{
            es[cnt][x] = 1;
            di[cnt][x]=1;
        }

    }

    int t;
    for (int i=1;i<=k;i++){
        cin >> t;
        pii srch = {t+1, -1};
        int pos = upper_bound(ord.begin(), ord.end(), srch) - ord.begin() - 1;
        if (pos<0) continue;
        int v = count[pos];
        r = r^di[v];
        r = r&es[v];
        // cerr << es[v][1] << ' ' << di[v][1] << '\n';

    }

    long long ss = 0;
    for (int i=1;i<=n;i++){
        if (r[i] == 1) ss += s[i];
        else ss+=l[i];
    }    

    cout << ss << '\n';

    return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i=0;i<ord.size();i++){
      |                  ~^~~~~~~~~~~

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