Submission #673249

#	Time	Username	Problem	Language	Result	Execution time	Memory
673249		Atlant	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	18 ms	21076 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool minn(T &A,T B){return A > B ? (A = B,1) : 0;}
template <class T> inline bool maxx(T &A,T B){return A < B ? (A = B,1) : 0;}
//#define int long long
#define task "c"
#define rep(i, n) for(int i = 0;i < n;++i)
#define FOR(i, l, r) for(int i = l; i <= r; ++i)
#define FOD(i, r, l) for(int i = r; i >= l; --i)
#define dem(x) __builtin_popcount(x)
#define endl '\n'
#define all(a) (a).begin(), (a).end()
#define pb emplace_back
#define SZ(x) (int)((x).size())
#define fi first
#define se second
typedef pair<int,int> ii;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
//const int base = 311;
//const int mod = 1e9 + 7;
const int N = 2e5 + 5; //
int a[N], b[N], n, m, p[N], t[N];
long long res;
struct IT{
    ii st[4*N];
    int sum[4*N];
    void build(int id = 1, int l = 1, int r = m){
        if(l == r){
            st[id] = {t[l], l};
            return;
        }
        int mid = l + r >> 1;
        build(id<<1, l, mid);
        build(id<<1|1, mid+1, r);
        st[id] = max(st[id<<1], st[id<<1|1]);
    }
    void add(int i, int id = 1, int l = 1, int r = m){
        if(l == r){
            st[id].fi = -1;
            sum[id] = 1;
            return;
        }
        int mid = l + r >> 1;
        if(i <= mid)add(i, id<<1, l, mid);
        else add(i, id<<1|1, mid+1, r);
        st[id] = max(st[id<<1], st[id<<1|1]);
        sum[id] = sum[id<<1] + sum[id<<1|1];
    }
    int pos(int x, int id = 1, int l = 1, int r = m){
        if(l == r)return l;
        int mid = l + r >> 1;
        return st[id<<1|1].fi >= x ? pos(x, id<<1|1, mid+1, r) : pos(x, id<<1, l, mid);
    }
    int get(int u, int v, int id = 1, int l = 1, int r = m){
        if(l > v or r < u)return 0;
        if(u <= l && r <= v)return sum[id];
        int mid = l + r >> 1;
        return get(u, v, id<<1, l, mid) + get(u, v, id<<1|1, mid+1, r);
    }
}seg;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
//         freopen(task".ans", "w", stdout);
    }
    cin >> n >> m;
    FOR(i, 1, n){
        cin >> a[i] >> b[i];
        p[i] = i;
    }
    sort(p + 1, p + 1 + n, [&](int i, int j){
        return max(a[i], b[i]) > max(b[i], b[j]);
    });
    FOR(i, 1, m)cin >> t[i];
    seg.build();
    FOR(i, 1, n){
        int Max = max(a[p[i]], b[p[i]]);
        int Min = min(a[p[i]], b[p[i]]);
        while(seg.st[1].fi >= Max)seg.add(seg.st[1].se);
        if(seg.st[1].fi >= Min){
            int j = seg.pos(Min);
            res += seg.get(j, m)&1 ? Min : Max;
            continue;
        }
        res += seg.sum[1]&1 ? b[p[i]] : a[p[i]];
    }
    cout << res;
}

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void IT::build(int, int, int)':
fortune_telling2.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'void IT::add(int, int, int, int)':
fortune_telling2.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'int IT::pos(int, int, int, int)':
fortune_telling2.cpp:52:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In member function 'int IT::get(int, int, int, int, int)':
fortune_telling2.cpp:58:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         int mid = l + r >> 1;
      |                   ~~^~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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