oj.uz

Submission #233688

# Submission time Handle Problem Language Result Execution time Memory
233688 2020-05-21T11:15:40 Z almogwald Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 8 ms 512 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define fort(i,a,b) forr(i,a,b,1)
#define forn(i,n) fort(i,1,n)
#define fori(i,n) fort(i,0,n)
#define forrb(i,a,b,c) for(int i=b-1;i>=a;i-=c)
#define fortb(i,a,b) forrb(i,a,b,1)
#define fornb(i,n) fortb(i,1,n)
#define forib(i,n) fortb(i,0,n)
using namespace std;
#define into(x) cin >> x;
typedef vector<int> veci;
typedef long long lol;
typedef pair<lol,lol> point;
#define def(x) lol x; into(x)

#define logn 20
int main() {
	ios::sync_with_stdio();
	def(n) def(m)
	vector<point> x,y;
	fori(i, n) {
		def(a) def(b)
			x.push_back({ a,b });
	}
	fori(i, m) {
		def(a)
			y.push_back({ a,i });
	}
	sort(y.begin(), y.end());
	vector<veci> arr(logn, veci(m+1));
	
	veci xx(m);
	set<point> r;
	forib(i, m) {
		int ii = y[i].second+1;
		int sum = 0;
		fori(j, logn) {
			if (ii % 2 == 1) {
				sum += arr[j][ii];
				ii++;
			}
			ii /= 2;
		}
		xx[i] = sum;
		ii = y[i].second;
		fori(j, logn) {
			arr[j][ii]++;
			ii /= 2;
		}
	}
	fori(i, m) {
		arr[0][i] = y[i].second;
	}
	forn(j, logn) {
		fori(i, (m / 2) + 1) {
			arr[j][i] = max(arr[j - 1][2 * i], arr[j - 1][2 * i + 1]);
		}
	}
	veci op(m);
	fori(i, m) {
		op[y[i].second] = i;
	}
	lol sum = 0;
	fori(i, n) {
		int low = 0, high = m - 1;
		int small = min(x[i].first, x[i].second);
		while (low < high) {
			int mid = (low + high) / 2;
			if (y[mid].first < small) {
				low = mid + 1;
			}
			else {
				high = mid;
			}
		}
		int lower = low;
		low = 0, high = m - 1;
		int big = max(x[i].first, x[i].second);
		while (low < high) {
			int mid = (low + high+1) / 2;
			if (y[mid].first >= big) {
				high = mid - 1;
			}
			else {
				low = mid;
			}
		}
		int higer = high;
		int best = -1;
		fori(j, logn) {
			if (lower > higer) {
				break;
			}
			if (lower % 2 == 1) {
				best = max(best,arr[j][lower]);
				lower++;
			}
			if (higer % 2 == 0) {
				best = max(best, arr[j][higer]);
				higer--;
				if (higer < 0) {
					break;
				}
			}
			lower /= 2;
			higer /= 2;
		}
		if (best == -1) {
			int num = m - lower;
			if (num % 2 == 1) {
				sum += x[i].second;
			}
			else {
				sum += x[i].first;
			}
		}
		else {
			int num = xx[op[best]];
			if (num % 2 == 1) {
				sum += small;
			}
			else {
				sum += big;
			}
		}
	}
	cout << sum << endl;
	return 0 ;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Incorrect 7 ms 512 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Incorrect 7 ms 512 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 7 ms 512 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 8 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 6 ms 512 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Incorrect 7 ms 512 KB Output isn't correct
12 Halted 0 ms 0 KB -