oj.uz

답안 #274052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
274052 2020-08-19T08:19:59 Z Falcon 운세 보기 2 (JOI14_fortune_telling2) C++14
35 / 100
 777 ms 262148 KB 
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#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 DEBUG
    #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>;

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;
	}
};

/*
class BIT{
	int n;
	vi a;

	void upd(int i, int v){
		for(i++; i <= n; i += i & -i)
			a[i] += v;
	}

public:
	inline BIT(int _n){
		n = _n;
		a.resize(n + 1);
	}

	inline void rupd(int l, int r){
		upd(l, 1), upd(r, -1);
	}

	int qry(int i) const{
		int s = 0;
		for(i++; i; i -= i & -i)
			s += a[i];
		return s;
	}
};
*/

class dynamicSegtree2D{ // I had to change this to Fenwick...

	class segtree1D{
		int n;
		struct node{
			int v = 0;
			node* l = 0;
			node* r = 0;
		};

		using pnode = node*;
		
		pnode root = 0;

		void update(pnode& t, int s, int e, int i, int v){
			if(i < s || e < i) return;
			if(!t) t = new node();
			t->v += v;
			debug(s, e, i, v, t->v);

			if(s != e)
				update(t->l, s, (s + e) >> 1, i, v), update(t->r, (s + e + 2) >> 1, e, i, v);
			
		}

		// [s, e]
		int query(pnode t, int s, int e, int l, int r){
			if(!t || r < s || e < l) return 0;
			debug(s, e, l, r, t->v);
			if(l <= s && e <= r) return t->v;
			else return query(t->l, s, (s + e) >> 1, l, r) + query(t->r, (s + e + 2) >> 1, e, l, r);
		}

	public:
		inline segtree1D(int _n = 0){ n = _n; }

		inline void update(int i, int v){ update(root, 0, n - 1, i, v); }

		inline int query(int l, int r){ return query(root, 0, n - 1, l, r); }

	};

	int n, k;
	vector<segtree1D> BIT;

	int pref(int i, int s, int e){
		int ans = 0;
		for(i++; i > 0; i -= i & -i)
			ans += BIT[i].query(s, e);
		return ans;
	}

public:
	inline dynamicSegtree2D(int _n, int _k){ n = _n; k = _k; BIT = vector<segtree1D>(n + 1, segtree1D(k)); }
	
	/*
	void update(int i, int j, int v){
		debug(i, j, v);
		for(i += n; i; i >>= 1){
			debug(i, j);
			seg[i].update(j, v);
		}
	}
	*/

	void update(int i, int j, int v){
		for(i++; i <= n; i += i & -i)
			BIT[i].update(j, v);
	}
	/*
	// [s1, e1], [s2, e2] and (1 -> index, 2 -> value)
	int query(int s1, int e1, int s2, int e2){
		int ans = 0;
		for(s1 += n, e1 += n + 1; s1 < e1; s1 >>= 1, e1 >>= 1){
			if(s1 & 1) {
				debug(s1, s2, e2, seg[s1].query(s2, e2));
				ans += seg[s1++].query(s2, e2);
			}
			if(e1 & 1) {
				debug(e1, seg[e1 - 1].query(s2, e2));
				ans += seg[--e1].query(s2, e2);
			}
		}
		return ans;
	}
	*/

	int query(int s1, int e1, int s2, int e2){
		return pref(e1, s2, e2) - pref(s1 - 1, s2, e2);
	}
};


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());
    dynamicSegtree2D seg2(K, compress.size());

    debug(T);
    rep(i, K) {
    	seg.update(T[i], i);
    	seg2.update(i, T[i], 1);
    }

    debug(seg2.query(0, K - 1, 1, compress.size() - 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]);
    	int k = seg2.query(t + 1, K - 1, r, compress.size() - 1);
    	debug(i, l, r, t, k);
    	if(k & 1) swap(A[i], B[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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 6 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct
8 Correct 4 ms 1408 KB Output is correct
9 Correct 4 ms 1408 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 4 ms 1408 KB Output is correct
12 Correct 5 ms 1408 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 6 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct
8 Correct 4 ms 1408 KB Output is correct
9 Correct 4 ms 1408 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 4 ms 1408 KB Output is correct
12 Correct 5 ms 1408 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct
14 Correct 77 ms 18808 KB Output is correct
15 Correct 150 ms 42268 KB Output is correct
16 Correct 270 ms 66904 KB Output is correct
17 Correct 352 ms 94456 KB Output is correct
18 Correct 330 ms 94424 KB Output is correct
19 Correct 321 ms 94332 KB Output is correct
20 Correct 346 ms 94328 KB Output is correct
21 Correct 311 ms 94328 KB Output is correct
22 Correct 263 ms 89592 KB Output is correct
23 Correct 264 ms 88696 KB Output is correct
24 Correct 249 ms 87492 KB Output is correct
25 Correct 263 ms 90704 KB Output is correct
26 Correct 312 ms 89336 KB Output is correct
27 Correct 356 ms 91512 KB Output is correct
28 Correct 293 ms 87800 KB Output is correct
29 Correct 350 ms 94328 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1408 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct
3 Correct 6 ms 1408 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 4 ms 1408 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct
8 Correct 4 ms 1408 KB Output is correct
9 Correct 4 ms 1408 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 4 ms 1408 KB Output is correct
12 Correct 5 ms 1408 KB Output is correct
13 Correct 4 ms 1408 KB Output is correct
14 Correct 77 ms 18808 KB Output is correct
15 Correct 150 ms 42268 KB Output is correct
16 Correct 270 ms 66904 KB Output is correct
17 Correct 352 ms 94456 KB Output is correct
18 Correct 330 ms 94424 KB Output is correct
19 Correct 321 ms 94332 KB Output is correct
20 Correct 346 ms 94328 KB Output is correct
21 Correct 311 ms 94328 KB Output is correct
22 Correct 263 ms 89592 KB Output is correct
23 Correct 264 ms 88696 KB Output is correct
24 Correct 249 ms 87492 KB Output is correct
25 Correct 263 ms 90704 KB Output is correct
26 Correct 312 ms 89336 KB Output is correct
27 Correct 356 ms 91512 KB Output is correct
28 Correct 293 ms 87800 KB Output is correct
29 Correct 350 ms 94328 KB Output is correct
30 Runtime error 777 ms 262148 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -