oj.uz

Submission #25393

# Submission time Handle Problem Language Result Execution time Memory
25393 2017-06-22T00:14:33 Z kajebiii Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 706 ms 54852 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

int mySum(int a, int b) {return a+b;}
int myMax(int a, int b) {return max(a, b);}
struct IDX {
	int P; vector<int> val;
	int initV;
	function<int(int, int)> f;
	IDX(int n, function<int(int, int)> ff) {
		for(P=1; P<n; P<<=1);
		val = vector<int>(2*P);
		f = ff;
	}
	void init(int v) {
		initV = v;
		val = vector<int>(2*P, v);
	}
	void update(int v, int k) {
		v += P;
		val[v] = f(val[v], k);
		while(v/=2) val[v] = f(val[v*2], val[v*2+1]);
	}
	int getF(int a, int b) {
		a += P; b += P;
		int res = initV;
		while(a<=b) {
			if(a%2==1) res = f(res, val[a++]);
			if(b%2==0) res = f(res, val[b--]);
			a>>=1;b>>=1;
		}
		return res;
	}
};
struct IDXNR {
	int P; vector<vector<int>> val;
	IDXNR(int n, int q[]) {
		for(P=1; P<n; P<<=1);
		val = vector<vector<int>>(2*P);
		for(int i=0; i<n; i++) val[P+i].push_back(q[i]);
		for(int i=P-1; i>=1; i--) {
			for(int x : val[i*2]) val[i].push_back(x);
			for(int x : val[i*2+1]) val[i].push_back(x);
			sort(ALL(val[i]));
		}
	}
	int getK(int a, int b, int k) {
		a += P; b += P;
		int res = 0;
		while(a<=b) {
			if(a%2==1) res += val[a].end() - lower_bound(ALL(val[a]), k), a++;
			if(b%2==0) res += val[b].end() - lower_bound(ALL(val[b]), k), b--;
			a>>=1;b>>=1;
		}
		return res;
	}
};

const int MAX_N = 2e5 + 100;

int N, Nr[MAX_N][2], Q[MAX_N], K;
vector<int> Co;
int main() {
	cin >> N >> K;
	REP(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Co.push_back(Nr[i][j]);
	REP(i, K) scanf("%d", &Q[i]), Co.push_back(Q[i]);
	sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end());
	REP(i, N) REP(j, 2) Nr[i][j] = lower_bound(ALL(Co), Nr[i][j]) - Co.begin();
	REP(i, K) Q[i] = lower_bound(ALL(Co), Q[i]) - Co.begin();

	IDX idxM = IDX(SZ(Co), myMax); idxM.init(-INF);
	REP(i, K) idxM.update(Q[i], i);
	IDXNR idxnr = IDXNR(K, Q);

	ll ans = 0;
	REP(i, N) {
		int minV = min(Nr[i][0], Nr[i][1]), maxV = max(Nr[i][0], Nr[i][1]);
		int ix = idxM.getF(minV, maxV-1);
		if(ix < 0) ix = 0; else Nr[i][0] = maxV, Nr[i][1] = minV;
		int cnt = idxnr.getK(ix, K-1, maxV);
		if(cnt % 2) swap(Nr[i][0], Nr[i][1]);
		ans += Co[Nr[i][0]];
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:77:68: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REP(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Co.push_back(Nr[i][j]);
                                                                    ^
fortune_telling2.cpp:78:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REP(i, K) scanf("%d", &Q[i]), Co.push_back(Q[i]);
                                                  ^

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6700 KB Output is correct
2 Correct 46 ms 9144 KB Output is correct
3 Correct 73 ms 10984 KB Output is correct
4 Correct 106 ms 13980 KB Output is correct
5 Correct 103 ms 13980 KB Output is correct
6 Correct 103 ms 13980 KB Output is correct
7 Correct 96 ms 13980 KB Output is correct
8 Correct 93 ms 13980 KB Output is correct
9 Correct 89 ms 13980 KB Output is correct
10 Correct 86 ms 13468 KB Output is correct
11 Correct 93 ms 13468 KB Output is correct
12 Correct 86 ms 13980 KB Output is correct
13 Correct 96 ms 13980 KB Output is correct
14 Correct 143 ms 13980 KB Output is correct
15 Correct 103 ms 13980 KB Output is correct
16 Correct 126 ms 13980 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 45636 KB Output is correct
2 Correct 383 ms 48708 KB Output is correct
3 Correct 499 ms 48708 KB Output is correct
4 Correct 616 ms 54852 KB Output is correct
5 Correct 319 ms 45636 KB Output is correct
6 Correct 596 ms 54852 KB Output is correct
7 Correct 643 ms 54852 KB Output is correct
8 Correct 643 ms 54852 KB Output is correct
9 Correct 706 ms 54852 KB Output is correct
10 Correct 689 ms 54852 KB Output is correct
11 Correct 603 ms 54852 KB Output is correct
12 Correct 579 ms 54852 KB Output is correct
13 Correct 636 ms 54852 KB Output is correct
14 Correct 526 ms 54852 KB Output is correct
15 Correct 496 ms 54852 KB Output is correct
16 Correct 513 ms 54852 KB Output is correct
17 Correct 496 ms 50756 KB Output is correct
18 Correct 489 ms 48704 KB Output is correct
19 Correct 579 ms 50756 KB Output is correct
20 Correct 586 ms 50756 KB Output is correct