Submission #1040851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040851		minhquaanz	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	3 ms	21084 KiB

fortune_telling2

/*Code by TMQ*/
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define task "1"
#define ii pair<ll, ll >
#define fi first
#define se second
#define pb push_back
#define em emplace
#define all(x) (x).begin(), (x).end()
#define sall(x) sort(all(x))
#define rall(x) reverse(all(x))
#define reset(a, x) (memset(a, x, sizeof(a)));
#define testcase ll tc; cin >> tc; while(tc--) solve();
ll inline gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); }
ll inline lcm(ll a, ll b) { return (a / gcd(a, b) * b); }
///============================================================================
#define BIT(i,mask) ((mask >> (i-1)) & 1)
#define DAOBIT(i,mask) ((mask ^ (1<<i-1))) 
#define OFFBIT(i,mask) ((mask & ~(1 << (i - 1))))
#define ONBIT(i,mask) ((mask | (1 << (i - 1)))) 
///============================================================================
const ll  mod = 1000000007;
const ll mod1 = 998244353;
const ll inf = 1000000000000000000 + 10;
const ll nmax = 200002;
///============================================================================
using namespace std;
///============================================================================
ll a[nmax][2], query[nmax];
ll n, k;
ll res;
vector<ll> t[nmax * 4];
vector<ll> operator +(vector<ll>& a, vector<ll>& b)
{
    vector<ll> ans;
    ll i, j;
    i = j = 0;
    while (i < a.size() && j < b.size())
    {
        if (a[i] < b[j])
            ans.pb(a[i++]);
        else ans.pb(b[j++]);
    }
    for (; i < a.size(); ++i)
        ans.pb(a[i]);
    for (; j < b.size(); ++j)
        ans.pb(b[j]);
    return ans;
}
void build(int k, int l, int r) {
    if (l == r) {
        t[k] = { query[l] };
        return;
    }
    int i1 = 0, i2 = 0, id1 = k << 1, id2 = k << 1 | 1, s1, s2, m = (l + r) >> 1;
    build(id1, l, m);
    build(id2, m + 1, r);

    s1 = t[id1].size();
    s2 = t[id2].size();

    while (i1 != s1 && i2 != s2)
        if (t[id1][i1] > t[id2][i2])
            t[k].pb(t[id2][i2++]);
        else
            t[k].pb(t[id1][i1++]);
    while (i1 != s1)
        t[k].pb(t[id1][i1++]);
    while (i2 != s2)
        t[k].pb(t[id2][i2++]);
}
ii get(int k, int l, int r, int f, int s) {
    ///cout << '\n' << '\n';
    auto it = lower_bound(all(t[k]), min(f, s));
    if (it == t[k].end())
    {
        ////cerr << t[k].end() - it << '\n';
        return { 0, 0 };
    }

    if (*it >= max(f, s))
    {
        ///cerr << t[k].end() - it << '\n';
        return { 0, t[k].end() - it };
    }

    if (l == r)
        return { 1, 0 };
    int m = (l + r) >> 1;
    auto r2 = get(k << 1 | 1, m + 1, r, f, s);
    if (r2.fi) return r2;
    auto r1 = get(k << 1, l, m, f, s);
    return { r1.fi, r1.se ^ r2.se };
}
///============================================================================
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ///freopen(task".inp", "r", stdin);
    ///freopen(task".outt", "w", stdout);
    cin >> n >> k;
    for (ll i = 1; i <= n; i++)
        cin >> a[i][0] >> a[i][1];
    for (ll i = 1; i <= k; i++)
        cin >> query[i];
    ///build(1, k);
    build(1, 1, k);
    // for (auto x : t[1])
    //     cout << x << ' ';
    for (ll i = 1; i <= n; i++)
    {
        ii ans = get(1, 1, n, a[i][0], a[i][1]);
        ////cerr << ans.fi << ' ' << ans.se << '\n';
        if (ans.fi > 0 && a[i][0] < a[i][1])
            swap(a[i][0], a[i][1]);
        res += a[i][ans.se & 1];
    }
    cout << res;
    return 0;

}

Compilation message (stderr)

fortune_telling2.cpp: In function 'std::vector<long long int> operator+(std::vector<long long int>&, std::vector<long long int>&)':
fortune_telling2.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while (i < a.size() && j < b.size())
      |            ~~^~~~~~~~~~
fortune_telling2.cpp:41:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     while (i < a.size() && j < b.size())
      |                            ~~^~~~~~~~~~
fortune_telling2.cpp:47:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (; i < a.size(); ++i)
      |            ~~^~~~~~~~~~
fortune_telling2.cpp:49:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (; j < b.size(); ++j)
      |            ~~^~~~~~~~~~

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