Submission #169487

#	Time	Username	Problem	Language	Result	Execution time	Memory
169487		tcm	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	1236 ms	55844 KiB

fortune_telling2

#include <bits/stdc++.h>
#define fname "FORTELL2"
#define bug(x) cerr << (#x) << " = " << (x) << '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define ui unsigned int
#define REP0(i, n) for(int i = 0, _n = (n); i < _n; ++i)
#define REP1(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define REPB0(i, n) for(int i = (n) - 1; i >= 0; --i)
#define REPB1(i, n) for(int i = (n); i > 0; --i)
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORB(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ARR0(a, n) {cerr <<(#a)<< ": ["; REP0(i, n) cerr<< ' ' << a[i] <<','; cerr<<"]\n";}
#define ARR1(a, n) {cerr <<(#a)<< ": ["; REP1(i, n) cerr<< ' ' << a[i] <<','; cerr<<"]\n";}
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ins insert
#define ers erase
#define LB lower_bound
#define UB upper_bound
#define X first
#define Y second

using namespace std;
template<typename T, typename V>
inline void bugp(const pair<T, V> &x) {cerr << '{' << x.X << ", " << x.Y << "}\n";}
template<typename T, typename U, typename V>
inline void bugpp(const pair<T, pair<U, V> > &x) {cerr << '{' << x.X << ", {" << x.Y.X << ", " << x.Y.Y << "}}\n";}
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef pair<float, float> ff;
typedef pair<int, ii> iii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef pair<ll, ii> lii;
const int N = 200002, K = 200002;
int n, k, sz, H[N+N+K], arr[N+N+K], Max[N+N+K << 2], ans[N], ind[K], fen[N+N+K];
ii coin[N];
struct Query {
    int C, id;
    bool operator <(const Query &qq) const {return C > qq.C;}
} Q[K];
struct Que {
    int val, L, R, id;
    bool operator <(const Que &qq) const {return val > qq.val;}
} data[N];

inline bool cmp(const Query &q1, const Query &q2) {return q1.id < q2.id;}
void compress()
{
    set<int> s;
    REP1(i, n) {
        s.ins(coin[i].X);
        s.ins(coin[i].Y);
    }
    REP1(i, k) s.ins(Q[i].C);
    vector<int> tmp(s.begin(), s.end());
    int temp;
    REP1(i, n) {
        temp = LB(tmp.begin(), tmp.end(), coin[i].X) - tmp.begin() + 1;
        H[temp] = coin[i].X;
        coin[i].X = temp;
        temp = LB(tmp.begin(), tmp.end(), coin[i].Y) - tmp.begin() + 1;
        H[temp] = coin[i].Y;
        coin[i].Y = temp;
    }
    REP1(i, k) {
        Q[i].C = LB(tmp.begin(), tmp.end(), Q[i].C) - tmp.begin() + 1;
        arr[Q[i].C] = i;
    }
    sz = tmp.size();
}
void build(int x = 1, int l = 1, int r = sz)
{
    if(l == r) Max[x] = arr[l];
    else {
        int mid = (l + r) >> 1;
        build(x << 1, l, mid);
        build(x << 1 | 1, mid + 1, r);
        Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
    }
}
int getMax(int u, int v, int x = 1, int l = 1, int r = sz)
{
    if(u > r || v < l) return INT_MIN;
    else if(u <= l && r <= v) return Max[x];
    int mid = (l + r) >> 1;
    return max(getMax(u, v, x << 1, l, mid), getMax(u, v, x << 1 | 1, mid + 1, r));
}
void update(int i) {for(; i <= sz; i += i&-i) ++fen[i];}
int getSum(int u, int v)
{
    int fi = 0, se = 0;
    --u;
    for(; u; u &= u - 1) fi += fen[u];
    for(; v; v &= v - 1) se += fen[v];
    return se - fi;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
    scanf("%d %d", &n, &k);
    REP1(i, n) scanf("%d %d", &coin[i].X, &coin[i].Y);
    REP1(i, k) {
        scanf("%d", &Q[i].C);
        Q[i].id = i;
    }
    compress();
    build();
    int pos, x, y, cnt = 0;
    REP1(i, n) {
        if(coin[i].X == coin[i].Y) ans[i] = H[coin[i].X];
        else {
            x = min(coin[i].X, coin[i].Y);
            y = max(coin[i].X, coin[i].Y);
            pos = getMax(x, y - 1);
            if(pos == k) ans[i] = H[y];
            else if(!pos) data[++cnt] = {coin[i].X, pos + 1, k, i};
            else data[++cnt] = {y, pos + 1, k, i};
        }
    }
    sort(data + 1, data + cnt + 1);
    sort(Q + 1, Q + k + 1);
    REP1(i, k) ind[i] = Q[i].id;
    sort(Q + 1, Q + k + 1, cmp);
    int j = 1, res;
    REP1(i, cnt) {
        while(Q[ind[j]].C >= data[i].val && j <= k) update(ind[j++]);
        res = getSum(data[i].L, data[i].R);
        if(res&1) {
            if(data[i].val == coin[data[i].id].X)
                ans[data[i].id] = H[coin[data[i].id].Y];
            else ans[data[i].id] = H[coin[data[i].id].X];
        }
        else ans[data[i].id] = H[data[i].val];
    }
    ll sum = 0;
    REP1(i, n) sum += ans[i];
    cout << sum;
	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp:40:44: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
 int n, k, sz, H[N+N+K], arr[N+N+K], Max[N+N+K << 2], ans[N], ind[K], fen[N+N+K];
                                         ~~~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:106:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:107:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     REP1(i, n) scanf("%d %d", &coin[i].X, &coin[i].Y);
                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &Q[i].C);
         ~~~~~^~~~~~~~~~~~~~~

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