oj.uz

Submission #274174

# Submission time Handle Problem Language Result Execution time Memory
274174 2020-08-19T09:26:31 Z Falcon Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 447 ms 30040 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;
using namespace __gnu_pbds;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef XDEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

template<typename T>
T& ckmin(T& a, T b){ return a = a > b ? b : a; }

template<typename T>
T& ckmax(T& a, T b){ return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using ordered_multiset = tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>;

class Compress{
	vi vals;

public:
	inline int rank(int x) const{
		return lower_bound(all(vals), x) - vals.begin();
	}

	Compress(vi& v){
		vals = v;
		sort(all(vals));
		vals.erase(unique(all(vals)), vals.end());
		for(auto& x : v) x = rank(x);
	}

	inline int size() const{
		return vals.size();
	}
};


class segtree{
	int n;
	vi seg;

	inline void pull(int i){
		seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
	}

public:
	inline segtree(int _n){
		n = _n;
		seg.resize(n << 1);
		fill(all(seg), -1);
	}

	void update(int i, int v){
		for(ckmax(seg[i += n], v), i >>= 1; i; i >>= 1)
			pull(i);
	}

	// [s, e)
	int query(int s, int e) const{
		int m = -1;
		for(s += n, e += n; s < e; s >>= 1, e >>= 1){
			if(s & 1) ckmax(m, seg[s++]);
			if(e & 1) ckmax(m, seg[--e]);
		}
		return m;
	}
};


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    #ifdef DEBUG
        freopen("debug", "w", stderr);
    #endif
    
    int N, K;
    cin >> N >> K;
    vi A(N), B(N), T(K);
    rep(i, N) cin >> A[i] >> B[i];
    rep(i, K) cin >> T[i];

    Compress compress(T);
    segtree seg(compress.size());

    debug(T);
    rep(i, K) seg.update(T[i], i);

    struct query{ int r, i; };

    vector<vector<query>> qs(K + 1);
    rep(i, N){
    	int l = compress.rank(A[i]);
    	int r = compress.rank(B[i]);
    	if(l > r) swap(l, r);
    	int t = seg.query(l, r);
    	if(t != -1 && A[i] < B[i]) swap(A[i], B[i]);
    	debug(i, t, l, r)
    	qs[t + 1].pb({r, i});
    }


    ordered_multiset S;
    rep3(i, K - 1, 0, -1){
    	S.insert({T[i], i});
    	for(auto& q : qs[i]){
    		if((K - i - S.order_of_key({q.r, -1})) & 1)
    			swap(A[q.i], B[q.i]);
    	}
    }

    cout << accumulate(all(A), 0LL) << '\n';

    #ifdef DEBUG
        dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 14 ms 1908 KB Output is correct
15 Correct 28 ms 3320 KB Output is correct
16 Correct 44 ms 4856 KB Output is correct
17 Correct 60 ms 6252 KB Output is correct
18 Correct 60 ms 6260 KB Output is correct
19 Correct 57 ms 6264 KB Output is correct
20 Correct 58 ms 6360 KB Output is correct
21 Correct 57 ms 6196 KB Output is correct
22 Correct 52 ms 5624 KB Output is correct
23 Correct 47 ms 5748 KB Output is correct
24 Correct 51 ms 5624 KB Output is correct
25 Correct 52 ms 5748 KB Output is correct
26 Correct 51 ms 6248 KB Output is correct
27 Correct 58 ms 6392 KB Output is correct
28 Correct 57 ms 6392 KB Output is correct
29 Correct 65 ms 6416 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 14 ms 1908 KB Output is correct
15 Correct 28 ms 3320 KB Output is correct
16 Correct 44 ms 4856 KB Output is correct
17 Correct 60 ms 6252 KB Output is correct
18 Correct 60 ms 6260 KB Output is correct
19 Correct 57 ms 6264 KB Output is correct
20 Correct 58 ms 6360 KB Output is correct
21 Correct 57 ms 6196 KB Output is correct
22 Correct 52 ms 5624 KB Output is correct
23 Correct 47 ms 5748 KB Output is correct
24 Correct 51 ms 5624 KB Output is correct
25 Correct 52 ms 5748 KB Output is correct
26 Correct 51 ms 6248 KB Output is correct
27 Correct 58 ms 6392 KB Output is correct
28 Correct 57 ms 6392 KB Output is correct
29 Correct 65 ms 6416 KB Output is correct
30 Correct 286 ms 23072 KB Output is correct
31 Correct 349 ms 24436 KB Output is correct
32 Correct 337 ms 26364 KB Output is correct
33 Correct 423 ms 29804 KB Output is correct
34 Correct 249 ms 22648 KB Output is correct
35 Correct 410 ms 29884 KB Output is correct
36 Correct 409 ms 29836 KB Output is correct
37 Correct 435 ms 29832 KB Output is correct
38 Correct 429 ms 29804 KB Output is correct
39 Correct 430 ms 30040 KB Output is correct
40 Correct 402 ms 29420 KB Output is correct
41 Correct 411 ms 29932 KB Output is correct
42 Correct 447 ms 29944 KB Output is correct
43 Correct 371 ms 28988 KB Output is correct
44 Correct 326 ms 29040 KB Output is correct
45 Correct 394 ms 29012 KB Output is correct
46 Correct 411 ms 27440 KB Output is correct
47 Correct 367 ms 27512 KB Output is correct
48 Correct 388 ms 30016 KB Output is correct
49 Correct 362 ms 29796 KB Output is correct