#include<bits/stdc++.h>
using namespace std;
#define int long long
const int T = 1048576;
const int INF = 1e18;
vector<int > ab;
void upd(int nde)
{
ab[nde] = max(ab[nde *2], ab[nde*2 +1]);
if(nde > 1)
upd(nde /2);
}
void setValue(int nde, int val)
{
ab[nde+T] = val;
upd((nde+T)/2);
}
int query(int nde, int RB, int RE, int GB, int GE)
{
if(GB > RE || RB > GE)
return -INF;
if(RB >= GB && RE <= GE)
return ab[nde];
int mid = (RB + RE)/2;
return max(query(nde *2, RB, mid, GB, GE), query(nde*2 +1, mid+1, RE, GB, GE));
}
vector<int > ab2;
void upd2(int nde)
{
ab2[nde] = ab2[nde *2] + ab2[nde*2 +1];
if(nde > 1)
upd(nde /2);
}
void addRange(int nde, int RB, int RE, int GB, int GE, int val)
{
//printf("%lld %lld %lld %lld %lld %lld \n", nde, RB, RE, GB, GE, val);
if(GB > RE || RB > GE)
return;
if(RB >= GB && RE <= GE)
{
ab2[nde] += val;
return;
}
int mid = (RB + RE)/2;
addRange(nde *2, RB, mid, GB, GE, val);
addRange(nde*2 +1, mid+1, RE, GB, GE, val);
}
int getValue(int pos)
{
int ans = 0;
pos += T;
while (pos >= 1)
{
ans += ab2[pos];
pos/=2;
}
return ans;
}
signed main()
{
int N, K;
scanf("%lld%lld", &N, &K);
vector<pair<int, int>> data;
vector<int > queries(K);
vector<int> original(1000000);
map<int, int> compressed;
set<int> values;
for(int iN = 0; iN < N; iN ++)
{
int Ai, Bi;
scanf("%lld %lld", &Ai, &Bi);
data.push_back({Ai, Bi});
values.insert(Ai);
values.insert(Bi);
}
for(int iQ = 0; iQ< K; iQ++)
{
int Ti;
scanf("%lld", &Ti);
queries[iQ] = Ti;
values.insert(Ti);
}
int idAct = 1;
for(int val : values)
{
compressed[val] = idAct;
original[idAct] = val;
idAct+=2;
}
vector<int> rotaInit(N, 0);
vector<pair<int, int>> inters;
vector<pair<int, int> > whenStop;
vector<pair<int, int>> cards(N);
vector<int> ans(N, -INF);
ab.assign(2*T, -INF); ab2.assign(2*T, 0);
for(int iK = 0; iK<K; iK++)
{
queries[iK] = compressed[queries[iK]];
setValue(queries[iK], iK);
}
for(int iN = 0; iN< N; iN++)
{
int deb = compressed[data[iN].first];
int fin = compressed[data[iN].second];
if(deb > fin)
{
swap(deb, fin);
rotaInit[iN]++;
}
cards[iN] = {deb, fin};
int lastMX = query(1, 0, T-1, deb, fin-1);
if(lastMX!=-INF)
{
//printf("card %lld : last end = query nu. %lld\n", iN, lastMX);
whenStop.push_back({lastMX, iN});
}
}
sort(whenStop.begin(), whenStop.end(), greater<pair<int, int>>());
int posiWS = 0;
for(int iQ = K-1; iQ >= 0; iQ--)
{
while (posiWS< whenStop.size() && whenStop[posiWS].first == iQ)
{
int iN = whenStop[posiWS].second;
ans[iN]=getValue(compressed[max(cards[iN].first, cards[iN].second)])+1;//+1 bc on commence au max instant
//printf("ans[%lld]=%lld\n", iN, ans[iN]);
posiWS++;
}
addRange(1, 0, T-1, 0, queries[iQ], 1);
}
int ansTot = 0;
for(int iN=0; iN<N; iN++)
{
if(ans[iN]==-INF)
{
ans[iN] = rotaInit[iN] + getValue(compressed[max(data[iN].first, data[iN].second)]);
}
//printf("%lld:%lld | %lld/%lld\n", iN, ans[iN], original[cards[iN].first], original[cards[iN].second]);
if(ans[iN]%2 == 0)
ansTot += original[cards[iN].first];
else
ansTot += original[cards[iN].second];
}
printf("%lld\n", ansTot);
}
Compilation message
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:137:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | while (posiWS< whenStop.size() && whenStop[posiWS].first == iQ)
| ~~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | scanf("%lld%lld", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
83 | scanf("%lld %lld", &Ai, &Bi);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%lld", &Ti);
| ~~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
41048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
41048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
41048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
