Submission #76733

#	Time	Username	Problem	Language	Result	Execution time	Memory
76733		kdh9949	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	859 ms	59956 KiB

fortune_telling2

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

using ll = long long;
#define all(v) (v).begin(),(v).end()

const int N = 200005, sz = 262144;
int n, m, a[N], b[N], c[N], t[N], x[N];
ll r;

struct Seg{
    vector<int> v[2 * sz];
    int u(int x, int y){
        for(x += sz; x; x >>= 1) v[x].push_back(y);
    }
    int m(int s, int e){
        int r = 0;
        for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
            if( s & 1){ if(!v[s].empty()) r = max(r, v[s].back()); s++; }
            if(~e & 1){ if(!v[e].empty()) r = max(r, v[e].back()); e--; }
        }
        return r;
    }
    int c(int s, int e, int x){
        int r = 0;
        for(s += sz, e += sz; s <= e; s >>= 1, e >>= 1){
            if( s & 1){ r ^= int(v[s].end() - lower_bound(all(v[s]), x)); s++; }
            if(~e & 1){ r ^= int(v[e].end() - lower_bound(all(v[e]), x)); e--; }
        }
        return r & 1;
    }
} S;

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", a + i, b + i);
        if(a[i] > b[i]){ c[i] = 1; swap(a[i], b[i]); }
    }
    for(int i = 1; i <= m; i++){
        scanf("%d", t + i);
        x[i - 1] = t[i];
    }
    sort(x, x + m);
    for(int i = 1; i <= m; i++){
        t[i] = int(lower_bound(x, x + m, t[i]) - x + 1);
        S.u(t[i], i);
    }
    for(int i = 1; i <= n; i++){
        int p = int(lower_bound(x, x + m, a[i]) - x + 1);
        int q = int(lower_bound(x, x + m, b[i]) - x);
        int t = S.m(p, q);
        r += (S.c(q + 1, m, t + 1) ^ (!t & !c[i])) ? a[i] : b[i];
    }
    printf("%lld\n", r);
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'int Seg::u(int, int)':
fortune_telling2.cpp:15:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", a + i, b + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", t + i);
         ~~~~~^~~~~~~~~~~~~

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