Submission #1131231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131231		vladilius	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	1 ms	320 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int q, n; cin>>q>>n;
    vector<int> a(q + 1), b(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>a[i]>>b[i];
    }
    vector<int> x(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>x[i];
    }
    
    auto get = [&](int l, int r){
        int out = 0;
        for (int i = l; i <= r; i++){
            out = max(out, x[i]);
        }
        return out;
    };
    
    ll ans = 0;
    for (int i = 1; i <= q; i++){
        if (a[i] <= b[i]){
            vector<int> p = {0};
            int out = 0;
            for (int j = 1; j <= n; j++){
                if (b[i] <= x[j]){
                    out++;
                    p.pb(j);
                }
            }
            p.pb(n + 1);
            for (int j = 0; j + 1 < p.size(); j++){
                int l = p[j] + 1, r = p[j + 1] - 1;
                out += (get(l, r) >= a[i]);
            }
            ans += (out % 2) ? b[i] : a[i];
        }
        else {
            vector<int> p;
            int out = 0;
            for (int j = 1; j <= n; j++){
                if (a[i] <= x[j]){
                    out++;
                    p.pb(j);
                }
            }
            p.pb(n + 1);
            for (int j = 0; j + 1 < p.size(); j++){
                int l = p[j] + 1, r = p[j + 1] - 1;
                out += (get(l, r) >= b[i]);
            }
            ans += (out % 2) ? b[i] : a[i];
        }
    }
    
    cout<<ans<<"\n";
}

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