Submission #519075

#	Time	Username	Problem	Language	Result	Execution time	Memory
519075		badlad	운세 보기 2 (JOI14_fortune_telling2)	C++17	4 / 100	94 ms	61272 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, 1);
}

int querycnt(int l, int r){
    return query(l, r, seg[1], add, 0);
}


void solve(){

    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