#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 250;
const int mod = 1e9+7;
const ll base = 75;
const int inf = 1e9;
int m, n, t, b[N], d[N], lab[N], c[N];
int k, a[N], dp[N], lst[N], fe[N];
ll ans, tong;
vector<int> adj[N], g[N];
vector<int> vi;
string s[N];
bool vis[N];
bool cmp(const int& x, const int& y)
{
return d[x] > d[y];
}
void add(int id, int x)
{
for(; id; id -= id & -id)fe[id] += x;
}
int get(int id)
{
int res = 0;
for(; id <= m; id += id & -id)res += fe[id];
return res;
}
struct IT
{
int n;
vector<int> st;
IT(int _n)
{
n = _n;
st.resize(n*4+4, 0);
}
void build(int id, int l, int r, int pos, int x)
{
if(l == r)
{
st[id] = max(x, st[id]);
return;
}
int mid = (l+r)>>1;
if(pos <= mid)build(id<<1, l, mid, pos, x);
else build(id<<1|1, mid+1, r, pos, x);
st[id] = max(st[id<<1], st[id<<1|1]);
}
void build(int pos, int x)
{
build(1, 1, n, pos, x);
}
int get(int id, int l, int r, int u, int v)
{
if(u <= l && r <= v)return st[id];
if(u > r || l > v)return 0;
int mid = (l+r)>>1;
return max(get(id<<1, l, mid, u, v), get(id<<1|1, mid+1, r, u, v));
}
int get(int l, int r)
{
return get(1, 1, n, l, r);
}
};
void sol()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)cin >> a[i] >> b[i];
for(int i = 1; i <= m; i ++)
{
cin >> d[i];
vi.pb(d[i]);
}
sort(vi.begin(), vi.end());
vi.erase(unique(vi.begin(), vi.end()), vi.end());
IT it(m);
for(int i = 1; i <= m; i ++)
{
c[i] = lower_bound(vi.begin(), vi.end(), d[i]) - vi.begin() + 1;
it.build(c[i], i);
}
for(int i = 1; i <= n; i ++)
{
int l = lower_bound(vi.begin(), vi.end(), min(a[i], b[i])) - vi.begin() + 1;
int r = lower_bound(vi.begin(), vi.end(), max(a[i], b[i])) - vi.begin();
//cout << l <<" "<<r<<'\n';
if(l <= r)lst[i] = it.get(l, r);
adj[lst[i]].pb(i);
}
for(int i = m; i >= 0; i --)
{
for(int j: adj[i])
{
if(i && a[j] < b[j])swap(a[j], b[j]);
int r = lower_bound(vi.begin(), vi.end(), max(a[j], b[j])) - vi.begin() + 1;
k = get(r);
if(k&1)
{
ans += b[j];
//cout << b[j] <<" ";
}
else
{
//cout << a[j] <<" ";
ans += a[j];
}
//cout <<k<<" "<< r << '\n';
}
//cout << c[i] <<" "<< i << '\n';
if(i)add(c[i], 1);
}
cout << ans;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int test = 1;
//cin >> test;
while(test -- > 0)sol();
return 0;
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:132:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:133:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15948 KB |
Output is correct |
2 |
Correct |
9 ms |
16076 KB |
Output is correct |
3 |
Correct |
9 ms |
15992 KB |
Output is correct |
4 |
Correct |
11 ms |
15992 KB |
Output is correct |
5 |
Correct |
10 ms |
16028 KB |
Output is correct |
6 |
Correct |
10 ms |
16076 KB |
Output is correct |
7 |
Correct |
9 ms |
15992 KB |
Output is correct |
8 |
Correct |
8 ms |
15992 KB |
Output is correct |
9 |
Correct |
9 ms |
16128 KB |
Output is correct |
10 |
Correct |
10 ms |
15984 KB |
Output is correct |
11 |
Correct |
9 ms |
16076 KB |
Output is correct |
12 |
Correct |
9 ms |
16012 KB |
Output is correct |
13 |
Correct |
11 ms |
16076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15948 KB |
Output is correct |
2 |
Correct |
9 ms |
16076 KB |
Output is correct |
3 |
Correct |
9 ms |
15992 KB |
Output is correct |
4 |
Correct |
11 ms |
15992 KB |
Output is correct |
5 |
Correct |
10 ms |
16028 KB |
Output is correct |
6 |
Correct |
10 ms |
16076 KB |
Output is correct |
7 |
Correct |
9 ms |
15992 KB |
Output is correct |
8 |
Correct |
8 ms |
15992 KB |
Output is correct |
9 |
Correct |
9 ms |
16128 KB |
Output is correct |
10 |
Correct |
10 ms |
15984 KB |
Output is correct |
11 |
Correct |
9 ms |
16076 KB |
Output is correct |
12 |
Correct |
9 ms |
16012 KB |
Output is correct |
13 |
Correct |
11 ms |
16076 KB |
Output is correct |
14 |
Correct |
20 ms |
16724 KB |
Output is correct |
15 |
Correct |
32 ms |
17612 KB |
Output is correct |
16 |
Correct |
45 ms |
18304 KB |
Output is correct |
17 |
Correct |
57 ms |
19048 KB |
Output is correct |
18 |
Correct |
68 ms |
19056 KB |
Output is correct |
19 |
Correct |
60 ms |
19072 KB |
Output is correct |
20 |
Correct |
53 ms |
19044 KB |
Output is correct |
21 |
Correct |
56 ms |
19016 KB |
Output is correct |
22 |
Correct |
41 ms |
18564 KB |
Output is correct |
23 |
Correct |
44 ms |
18552 KB |
Output is correct |
24 |
Correct |
42 ms |
18544 KB |
Output is correct |
25 |
Correct |
41 ms |
18700 KB |
Output is correct |
26 |
Correct |
46 ms |
18880 KB |
Output is correct |
27 |
Correct |
67 ms |
19044 KB |
Output is correct |
28 |
Correct |
48 ms |
19088 KB |
Output is correct |
29 |
Correct |
55 ms |
19292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
15948 KB |
Output is correct |
2 |
Correct |
9 ms |
16076 KB |
Output is correct |
3 |
Correct |
9 ms |
15992 KB |
Output is correct |
4 |
Correct |
11 ms |
15992 KB |
Output is correct |
5 |
Correct |
10 ms |
16028 KB |
Output is correct |
6 |
Correct |
10 ms |
16076 KB |
Output is correct |
7 |
Correct |
9 ms |
15992 KB |
Output is correct |
8 |
Correct |
8 ms |
15992 KB |
Output is correct |
9 |
Correct |
9 ms |
16128 KB |
Output is correct |
10 |
Correct |
10 ms |
15984 KB |
Output is correct |
11 |
Correct |
9 ms |
16076 KB |
Output is correct |
12 |
Correct |
9 ms |
16012 KB |
Output is correct |
13 |
Correct |
11 ms |
16076 KB |
Output is correct |
14 |
Correct |
20 ms |
16724 KB |
Output is correct |
15 |
Correct |
32 ms |
17612 KB |
Output is correct |
16 |
Correct |
45 ms |
18304 KB |
Output is correct |
17 |
Correct |
57 ms |
19048 KB |
Output is correct |
18 |
Correct |
68 ms |
19056 KB |
Output is correct |
19 |
Correct |
60 ms |
19072 KB |
Output is correct |
20 |
Correct |
53 ms |
19044 KB |
Output is correct |
21 |
Correct |
56 ms |
19016 KB |
Output is correct |
22 |
Correct |
41 ms |
18564 KB |
Output is correct |
23 |
Correct |
44 ms |
18552 KB |
Output is correct |
24 |
Correct |
42 ms |
18544 KB |
Output is correct |
25 |
Correct |
41 ms |
18700 KB |
Output is correct |
26 |
Correct |
46 ms |
18880 KB |
Output is correct |
27 |
Correct |
67 ms |
19044 KB |
Output is correct |
28 |
Correct |
48 ms |
19088 KB |
Output is correct |
29 |
Correct |
55 ms |
19292 KB |
Output is correct |
30 |
Correct |
115 ms |
24004 KB |
Output is correct |
31 |
Correct |
143 ms |
24648 KB |
Output is correct |
32 |
Correct |
209 ms |
25716 KB |
Output is correct |
33 |
Correct |
279 ms |
27440 KB |
Output is correct |
34 |
Correct |
129 ms |
23956 KB |
Output is correct |
35 |
Correct |
314 ms |
27440 KB |
Output is correct |
36 |
Correct |
309 ms |
27500 KB |
Output is correct |
37 |
Correct |
282 ms |
27252 KB |
Output is correct |
38 |
Correct |
336 ms |
27508 KB |
Output is correct |
39 |
Correct |
283 ms |
27372 KB |
Output is correct |
40 |
Correct |
299 ms |
27136 KB |
Output is correct |
41 |
Correct |
300 ms |
27248 KB |
Output is correct |
42 |
Correct |
296 ms |
27264 KB |
Output is correct |
43 |
Correct |
197 ms |
27088 KB |
Output is correct |
44 |
Correct |
192 ms |
27136 KB |
Output is correct |
45 |
Correct |
193 ms |
27172 KB |
Output is correct |
46 |
Correct |
198 ms |
27216 KB |
Output is correct |
47 |
Correct |
197 ms |
27016 KB |
Output is correct |
48 |
Correct |
247 ms |
27312 KB |
Output is correct |
49 |
Correct |
256 ms |
27484 KB |
Output is correct |