#include <bits/stdc++.h>
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());
}
bool 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)%2;
}
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, 0)) - potentielsOperations.begin();
iDeb = potentielsOperations[iPos].second;
}
bool nbInv = seg.query(1, iDeb+1, nbOperations-1, grand);
int choisie = A;
if (A > B)
{
if (nbInv)
choisie = B;
}
else
{
if (iDeb == -1)
{
if (nbInv)
choisie = B;
}
else
{
if (!nbInv)
choisie = B;
}
}
sol += choisie;
}
cout << sol << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
