oj.uz

Submission #376375

# Submission time Handle Problem Language Result Execution time Memory
376375 2021-03-11T10:34:36 Z peijar Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 259 ms 71276 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;


struct countGreater
{
	vector<vector<int>> seg;
	vector<int> deb, fin;
	vector<int> valeurs;

	countGreater(const vector<int> &v) : valeurs(v)
	{
		int nbElem(1);
		while (nbElem < (int)v.size())
			nbElem *= 2;
		seg.resize(2 * nbElem), deb.resize(2*nbElem), fin.resize(2*nbElem);
		build(1, 0, (int)v.size()-1);
	}

	void build(int iNoeud, int iDeb, int iFin)
	{
		deb[iNoeud] = iDeb, fin[iNoeud] = iFin;
		if (iDeb == iFin)
		{
			seg[iNoeud] = {valeurs[iDeb]};
			return ;
		}
		int iMid = (iDeb + iFin) / 2;
		build(2*iNoeud, iDeb, iMid);
		build(2*iNoeud+1, iMid+1, iFin);
		seg[iNoeud].resize(seg[2*iNoeud].size() + seg[2*iNoeud+1].size());
		merge(seg[2*iNoeud].begin(), seg[2*iNoeud].end(),
				seg[2*iNoeud+1].begin(), seg[2*iNoeud+1].end(),
				seg[iNoeud].begin());
	}

	int query(int iNoeud, int debR, int finR, int borne)
	{
		if (debR > fin[iNoeud] or finR < deb[iNoeud])
			return 0;
		if (debR <= deb[iNoeud] and fin[iNoeud] <= finR)
		{
			int iPos = lower_bound(seg[iNoeud].begin(), seg[iNoeud].end(), borne)
				- seg[iNoeud].begin();
			return seg[iNoeud].size() - iPos;
		}
		return query(2*iNoeud, debR, finR, borne)
			+ query(2*iNoeud+1, debR, finR, borne);
	}
};

// Si Ai = Bi osef
// WLoG : Ai < Bi
// Si Tj >= Bi : swap. Si Tj < Ai : osef, sinon : on a toujours Bi apres
// On peut donc trouver le dernier j tq Ai <= Tj < Bi puis compter le nombre de k > j tq Tk >= Bi

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbCartes, nbOperations;
	cin >> nbCartes >> nbOperations;
	vector<pair<int, int>> cartes(nbCartes);
	for (auto &[A, B] : cartes)
		cin >> A >> B;

	vector<int> operations(nbOperations);
	for (auto &v : operations)
		cin >> v;
	sort(cartes.begin(), cartes.end(),
			[](pair<int, int> a, pair<int, int> b)
			{
				return max(a.first, a.second) < max(b.first,  b.second);
				});
	vector<pair<int, int>> potentielsOperations;
	vector<int> ordreOp(nbOperations);
	for (int i(0); i < nbOperations; ++i)
		ordreOp[i] = i;
	sort(ordreOp.begin(), ordreOp.end(),
			[&](int i, int j) { return operations[i] < operations[j]; });

	countGreater seg(operations);
	int curOp(0);
	int sol(0);
	for (auto [A, B] : cartes)
	{
		if (A == B)
		{
			sol += A;
			continue;
		}
		int grand = max(A, B);
		int petit = min(A, B);
		while (curOp < nbOperations and operations[ordreOp[curOp]] < grand)
		{
			while (!potentielsOperations.empty() and 
					potentielsOperations.back().second < ordreOp[curOp])
				potentielsOperations.pop_back();
			auto aAjouter = make_pair(operations[ordreOp[curOp]], ordreOp[curOp]);
			if (potentielsOperations.empty()
					or potentielsOperations.back().first != aAjouter.first)
				potentielsOperations.emplace_back(aAjouter);
			curOp++;
		}
		int iDeb = -1;
		if (!potentielsOperations.empty() and potentielsOperations.back().first >= petit)
		{
			int iPos = lower_bound(potentielsOperations.begin(), potentielsOperations.end(), make_pair(petit, 0LL)) - potentielsOperations.begin();
			iDeb = potentielsOperations[iPos].second;
		}
		int nbInv = seg.query(1, iDeb+1, nbOperations-1, grand);
		int choisie = A;
		if (A > B)
		{
			if (nbInv % 2)
				choisie = B;
		}
		else
		{
			if (iDeb == -1)
			{
				if (nbInv % 2)
					choisie = B;
			}
			else
			{
				if (!(nbInv % 2))
					choisie = B;
			}
		}
		//cout << A << ' ' << B << ' ' << choisie << ' ' << iDeb << ' ' << nbInv << endl;
		sol += choisie;
	}
	cout << sol << endl;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 11 ms 3820 KB Output is correct
15 Correct 28 ms 7404 KB Output is correct
16 Correct 42 ms 9836 KB Output is correct
17 Correct 46 ms 14828 KB Output is correct
18 Correct 45 ms 14828 KB Output is correct
19 Correct 45 ms 14828 KB Output is correct
20 Correct 49 ms 14828 KB Output is correct
21 Correct 43 ms 14700 KB Output is correct
22 Correct 41 ms 14316 KB Output is correct
23 Correct 43 ms 14316 KB Output is correct
24 Correct 41 ms 14316 KB Output is correct
25 Correct 37 ms 14444 KB Output is correct
26 Correct 49 ms 14572 KB Output is correct
27 Correct 51 ms 14828 KB Output is correct
28 Correct 49 ms 14828 KB Output is correct
29 Correct 52 ms 14956 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 11 ms 3820 KB Output is correct
15 Correct 28 ms 7404 KB Output is correct
16 Correct 42 ms 9836 KB Output is correct
17 Correct 46 ms 14828 KB Output is correct
18 Correct 45 ms 14828 KB Output is correct
19 Correct 45 ms 14828 KB Output is correct
20 Correct 49 ms 14828 KB Output is correct
21 Correct 43 ms 14700 KB Output is correct
22 Correct 41 ms 14316 KB Output is correct
23 Correct 43 ms 14316 KB Output is correct
24 Correct 41 ms 14316 KB Output is correct
25 Correct 37 ms 14444 KB Output is correct
26 Correct 49 ms 14572 KB Output is correct
27 Correct 51 ms 14828 KB Output is correct
28 Correct 49 ms 14828 KB Output is correct
29 Correct 52 ms 14956 KB Output is correct
30 Correct 150 ms 64328 KB Output is correct
31 Correct 169 ms 65772 KB Output is correct
32 Correct 190 ms 67564 KB Output is correct
33 Correct 253 ms 71236 KB Output is correct
34 Correct 148 ms 63980 KB Output is correct
35 Correct 247 ms 71020 KB Output is correct
36 Correct 241 ms 71276 KB Output is correct
37 Correct 251 ms 71020 KB Output is correct
38 Correct 240 ms 71020 KB Output is correct
39 Correct 259 ms 71020 KB Output is correct
40 Correct 221 ms 70764 KB Output is correct
41 Correct 252 ms 71148 KB Output is correct
42 Correct 251 ms 71020 KB Output is correct
43 Correct 205 ms 70380 KB Output is correct
44 Correct 200 ms 70380 KB Output is correct
45 Correct 204 ms 70252 KB Output is correct
46 Correct 210 ms 69140 KB Output is correct
47 Correct 233 ms 68972 KB Output is correct
48 Correct 254 ms 71240 KB Output is correct
49 Correct 242 ms 71132 KB Output is correct