Submission #372913

#	Time	Username	Problem	Language	Result	Execution time	Memory
372913		BartolM	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	548 ms	29520 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=2e5+5;
const int OFF=(1<<20);

int n, q;
vector <pii> v, vec[N];
vector <int> que, saz;
int desaz[3*N], sol[N], Tmax[2*OFF], T[2*OFF], br[N];
#define DEBUG 0

int sazmi(int x) {
    int ret=lower_bound(saz.begin(), saz.end(), x)-saz.begin();
    desaz[ret]=x;
    return ret;
}

int query_max(int a, int b, int pos=1, int lo=0, int hi=OFF) {
    if (lo>=a && hi<=b) return Tmax[pos];
    if (lo>=b || hi<=a) return -1;
    int mid=(lo+hi)/2;
    return max(query_max(a, b, pos*2, lo, mid), query_max(a, b, pos*2+1, mid, hi));
}

int query(int a, int b, int pos=1, int lo=0, int hi=OFF) {
    if (lo>=a && hi<=b) return T[pos];
    if (lo>=b || hi<=a) return 0;
    int mid=(lo+hi)/2;
    return query(a, b, pos*2, lo, mid)+query(a, b, pos*2+1, mid, hi);
}

void update(int pos, int x) {
    pos+=OFF; T[pos]+=x;
    pos/=2;
    while (pos) {
        T[pos]=T[pos*2]+T[pos*2+1];
        pos/=2;
    }
}

void build() {
    for (int i=OFF-1; i>0; --i) Tmax[i]=max(Tmax[i*2], Tmax[i*2+1]);
}

void solve() {
    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    memset(Tmax, -1, sizeof Tmax);

    for (int i=0; i<q; ++i) {
        que[i]=sazmi(que[i]);
        Tmax[OFF+que[i]]=i;
    }
    build();

    for (int i=0; i<n; ++i) {
        v[i].X=sazmi(v[i].X); v[i].Y=sazmi(v[i].Y);
        int mn=min(v[i].X, v[i].Y), mx=max(v[i].X, v[i].Y);
        int pos=query_max(mn, mx);
        br[i]=pos;
        vec[pos+1].pb(mp(mx, i));
    }
    for (int i=q-1; i>=0; --i) {
        update(que[i], 1);
        for (pii pp:vec[i]) sol[pp.Y]=query(pp.X, OFF);
    }
    #if DEBUG
        for (int i=0; i<n; ++i) {
            printf("%d %d\n", v[i].X, v[i].Y);
        }
        for (int x:que) printf("%d\n", x);
    #endif // DEBUG

    ll res=0;
    for (int i=0; i<n; ++i) {
        int curr;
        if (br[i]==-1) curr=sol[i]%2 ? v[i].Y : v[i].X;
        else {
            if (v[i].X>v[i].Y) swap(v[i].X, v[i].Y);
            curr=sol[i]%2 ? v[i].X : v[i].Y;
        }
        res+=desaz[curr];
        #if DEBUG
            printf("i: %d, pos: %d, sol: %d, curr: %d, koji: %d\n", i, br[i], sol[i], curr, desaz[curr]);
        #endif
    }
    printf("%lld\n", res);
}

void load() {
    scanf("%d %d", &n, &q);
    for (int i=0; i<n; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        saz.pb(a); saz.pb(b);
        v.pb(mp(a, b));
    }
    for (int i=0; i<q; ++i) {
        int x;
        scanf("%d", &x);
        que.pb(x); saz.pb(x);
    }
}

int main() {
    load();
    solve();
    return 0;
}

/*
1 4
7 8
8
6
5
3

*/

Compilation message (stderr)

fortune_telling2.cpp: In function 'void load()':
fortune_telling2.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

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