Submission #1113516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113516		lucascgar	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	252 ms	23760 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

query so na esquerda:
    desliga esquerda
    nn mexe em direita

depois de query na esquerda ele sempre vai ficar com direita ativa
olhar ultima query na esquerda
depois só importam queries na direita
*/

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

const int MAXN=2e5+10, MAXTT = 2*MAXN, BIG = 1e9+10;

pii c[MAXN];
bool ac[MAXN];

int seg[4*MAXN], lg[MAXN];

void build(int id, int il, int ir, vector<pii> &op){
    if (il==ir){
        seg[id]=op[il-1].second;
        return;
    }
    int m = (il+ir)/2;
    build(2*id, il, m, op);
    build(2*id+1, m+1, ir, op);
    seg[id] = max(seg[2*id], seg[2*id+1]);

}

int qry(int id, int il, int ir, int l, int r){
    if (il>r || ir<l) return -BIG;
    if (il>=l && ir<=r) return seg[id];

    int m = (il+ir)/2;
    return max(qry(2*id, il, m, l, r), qry(2*id+1, m+1, ir, l, r));
}

pii lst[MAXN];


int bit[MAXTT];

int bqry(int p){
    int ss = 0;
    while (p>0){
        ss += bit[p];
        p -= p&-p;
    }
    return ss;
}

void bup(int p, int v, int sz){
    while (p<=sz){
        bit[p]+=v;
        p += p&-p;
    }
}

int p[MAXN];

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

    int n, k;
    cin >> n >> k;
    int a, b;
    vector<pair<int, pii>> comp;
    for (int i=0;i<n;i++){
        cin >> a >> b;
        if (a<b) ac[i]=1;
        else if(a>b) swap(a,b);
        c[i] = {a,b}, lg[i]=b;
        comp.push_back({b,{i, 0}});
    }

    vector<pii> op(k);
    for (int i=0;i<k;i++){
        cin >> p[i+1];
        op[i] = {p[i+1], i+1};
        comp.push_back({p[i+1], {i+1, 1}});
    }

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

    build(1, 1, k, op);

    for (int i=0;i<n;i++){
        int l, r;
        pii srch = {c[i].second, -1};
        r = lower_bound(op.begin(), op.end(), srch) - op.begin(), srch = {c[i].first, -1}, l = lower_bound(op.begin(), op.end(), srch) - op.begin() + 1;

        if (l<=r) lst[i].first = qry(1, 1, k, l, r);
        lst[i].second = i;
    }

    sort(lst,lst+n);  // ordena por ultimo que importa

    // comprime qries com caras da direita
    sort(comp.begin(), comp.end());
    int cr = 1;
    for (int i=0;i<comp.size();i++){
        if (i>0 && comp[i].first != comp[i-1].first) cr++;
    
        if (comp[i].second.second) p[comp[i].second.first] = cr;
        else lg[comp[i].second.first] = cr;
    }

    int j = n-1;  // primeiro q nn pega

    for (int i=k;i>0&&j>=0;i--){
        // atualiza
        bup(cr-p[i]+1, 1, cr+1);

        while (j>=0 && lst[j].first == i){
            int am = bqry(cr-lg[lst[j].second]+1);
            // cerr << lst[j].second << ": " << am << " so " << ac[lst[j].second] << '\n';
            ac[lst[j].second] = (am%2 == 1);
            j--;
        }
    }
    while (j>=0){  // quem só pega no direito
        int am = bqry(cr-lg[lst[j].second]+1);
        ac[lst[j].second] ^= (am%2 == 1);
        // cerr << lst[j].second << ": " << am << " so " << ac[lst[j].second] << '\n';
        j--;
    }
    long long ss = 0;
    for (int i=0;i<n;i++){
        if (ac[i]) ss += c[i].first;
        else ss += c[i].second;
    }

    cout << ss << '\n';

    return 0;
}

Compilation message (stderr)

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

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