Submission #938428

#	Time	Username	Problem	Language	Result	Execution time	Memory
938428		Mohammadamin__Sh	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	615 ms	54832 KiB

fortune_telling2

//In His Name
#include <bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
using namespace std;
#define ll long long
//#define int ll
typedef pair<int, int> pii;
#define F first
#define S second
#define pb push_back
#define bug(x) cout << "Ah shit , here we go again : " << x <<endl
#define all(x) x.begin() , x.end()
const int maxn = 2e5+10 , MOD = 1e9 + 7;
const ll INF = 1e18 + 100;

int n , k , q[maxn];
ll ans;
pii c[maxn];
vector<int> tree[4*maxn];

void Build(int id = 1, int L = 1 , int R = k+1){
    if(L+1 == R){
        tree[id].pb(q[L]);
        return;
    }
    int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
    Build(lc , L , mid) , Build(rc , mid , R);
    for(int i : tree[lc]) tree[id].pb(i);
    for(int i : tree[rc]) tree[id].pb(i);
    sort(all(tree[id]));
}

int Find(int id , int L , int R , int l , int r){
    if(L+1 == R) return L;
    int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1;
    int low = lower_bound(all(tree[id]) , l) - tree[id].begin();
    if(low == tree[id].size() or tree[id][low] >= r) return 0;
    low = lower_bound(all(tree[rc]) , l) - tree[rc].begin();
    if(low < tree[rc].size() and tree[rc][low] < r) return Find(rc , mid , R , l , r);
    else return Find(lc , L , mid , l , r);
}

int Get(int id , int L , int R , int l , int r , int val){
    if(L == l and R == r) return tree[id].end() - lower_bound(all(tree[id]) , val);
    int mid = (L+R) >> 1 , lc = id << 1 , rc = lc | 1 , res = 0;
    if(l < mid) res += Get(lc , L , mid , l , min(mid , r) , val);
    if(r > mid) res += Get(rc , mid , R , max(l , mid) , r , val);
    return res;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);

    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++) cin >> c[i].F >> c[i].S;
    for(int i = 1 ; i <= k ; i++) cin >> q[i];
    Build();
    for(int i = 1 ; i <= n ; i++){
        int l = min(c[i].F , c[i].S);
        int r = max(c[i].F , c[i].S);
        int tah = Find(1 , 1 , k+1 , l , r);
        if(tah == k){
            ans += r;
            continue;
        }
        int num = Get(1 , 1 , k+1 , tah+1 , k+1 , r);
        if(tah == 0) ans += (num & 1 ? c[i].S : c[i].F);
        else{
            if(c[i].F >= c[i].S) ans += (num & 1 ? c[i].S : c[i].F);
            else ans += (num & 1 ? c[i].F : c[i].S);
        }
    }
    cout << ans;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int Find(int, int, int, int, int)':
fortune_telling2.cpp:38:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     if(low == tree[id].size() or tree[id][low] >= r) return 0;
      |        ~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(low < tree[rc].size() and tree[rc][low] < r) return Find(rc , mid , R , l , r);
      |        ~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65