Submission #519151

#	Time	Username	Problem	Language	Result	Execution time	Memory
519151		badlad	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	4 / 100	88 ms	60696 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, l, r) for(auto i=l; i<r; i++)
#define all(v) v.begin(), v.end()
#define nn '\n'
 
 
using vi = vector<int>;
using ll = long long;
 
struct node{
    int val = 0, c = -1, c2 = -1;
};
int nxt=2;
vector<node> seg((int)5e6+3);
 
 
int intersec(int l, int r, int l2, int r2){
    return min(r, r2) - max(l, l2) + 1;
}
 
int query(int ql, int qr, const node &cur, auto const &comb, int id, int l=1, int r=1e9){
    
    int mid = (l + r) / 2, res = id;
 
    if(intersec(l, r, ql, qr) == r - l + 1)
       return cur.val;
   
    if(cur.c != -1 && intersec(l, mid, ql, qr) > 0)
       comb(res, query(ql, qr, seg[cur.c], comb, id, l, mid));
 
    if(cur.c2 != -1 && intersec(mid+1, r, ql, qr) > 0)
       comb(res, query(ql, qr, seg[cur.c2], comb, id, mid+1, r));
 
    return res;
}
void upd(int pos, int nval, node &cur, auto const &comb, int id, int l=1, int r=1e9){
 
    int mid = (l + r) / 2;
    
    if(l == r){
       if(nval >= 0) cur.val = nval;
       else cur.val += -nval;
       return;
    }
    
    cur.val = id;
    if(intersec(l, mid, pos, pos) == 1){       
       
       if(cur.c == -1) cur.c = nxt++;
       
       seg[cur.c].val = id;
       upd(pos, nval, seg[cur.c], comb, id, l, mid);
    }
    else{
       if(cur.c2 == -1) cur.c2 = nxt++;
       
       seg[cur.c2].val = id; 
       upd(pos, nval, seg[cur.c2], comb, id, mid+1, r);
    }
 
    if(cur.c != -1)  comb(cur.val, seg[cur.c].val);
    if(cur.c2 != -1) comb(cur.val, seg[cur.c2].val);
 
}
 
void add(int &a, int b){ a += b; }
void cmax(int &a, int b){ a = max(a, b); }
 
void updmx(int pos, int nval){
    upd(pos, nval, seg[0], cmax, -1);
}
 
void updcnt(int pos){
    upd(pos, -1, seg[1], add, 0);
}
 
int querymx(int l, int r){
    return query(l, r, seg[0], cmax, -1);
}
 
int querycnt(int l, int r){
    return query(l, r, seg[1], add, 0);
}
 
 
void solve(){
 
    seg[0].val = -1;
    seg[1].val = 0;
 
    int n, k;
    cin >> n >> k;
 
 
    vector<int> a(n), b=a, t(k);
    
    rep(i, 0, n) cin >> a[i] >> b[i];
 
    rep(i, 0, k){ 
       cin >> t[i];
       updmx(t[i], i);
    }
    
    vi ind[k+1], flip(n);
    rep(i, 0, n){
       
       if(a[i] > b[i]){ swap(a[i], b[i]); flip[i] = 1; }
 
       int q = querymx(a[i], b[i]-1);
       ind[q+1].push_back(i);
    }
 
    for(int i=k-1; i>=0; i--){
       updcnt(t[i]);
       for(int j : ind[i+1])
          flip[j] = 1 - querycnt(b[j], 1e9) % 2;
    }
 
    for(int j : ind[0])
       flip[j] ^= querycnt(b[j], 1e9) % 2; 
 
    ll sum = 0;
    
    rep(i, 0, n){
       if(flip[i]) sum += b[i];
       else sum += a[i]; 
    }
 
    cout << sum;
    
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    solve();
}

Compilation message (stderr)

fortune_telling2.cpp:23:44: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | int query(int ql, int qr, const node &cur, auto const &comb, int id, int l=1, int r=1e9){
      |                                            ^~~~
fortune_telling2.cpp:38:40: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   38 | void upd(int pos, int nval, node &cur, auto const &comb, int id, int l=1, int r=1e9){
      |                                        ^~~~

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