This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
~~~~~^~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |