Submission #932958

#	Time	Username	Problem	Language	Result	Execution time	Memory
932958		sugartheanh	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	14 ms	25692 KiB

fortune_telling2

#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>

using namespace std;

#define task "test"
#define bit(s, i) ((s >> i) & 1)
#define all(v) v.begin(), v.end()
#define ii pair <int, int>
#define vii vector<ii>
#define vi vector <int>
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define eb emplace_back
#define pb push_back

void solve();

int32_t main()
{
	if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	double start = clock();

	int tc = 1;
	// cin >> tc;

	while(tc--)
	{
		solve();
	}

	cerr << "Elapsed time: " << ((double)clock() - start) / CLOCKS_PER_SEC * 1000 << " ms";
}

const int mod = 1e9+7;
const int inf = 1e9;
const ll infll = 1e18;

const int N = 2e5+5;

int n, k;
ii a[N], t[N];
vi rar;

struct segTree
{
    int st[N*12];

    segTree()
    {
        fill(st+1, st+1+N*12, 1);
    }

    void upd(int x, int v, int id=1, int l=1, int r=N*3)
    {
        if(x>r or x<l) return;
        if(l == r)
        {
            st[id] = v;
            return;
        }

        int mid = (l + r) >> 1;

        upd(x, v, id<<1, l, mid);
        upd(x, v, id<<1|1, mid+1, r);

        st[id] = max(st[id<<1], st[id<<1|1]);
    }

    int get(int u, int v, int id=1, int l=1, int r=N*3)
    {
        if(u>r or v<l) return 1;
        if(u<=l and r<=v)
        {
            return st[id];
        }

        int mid = (l + r) >> 1;

        return max(get(u, v, id<<1, l, mid), get(u, v, id<<1|1, mid+1, r));
    }       
} tree;

struct BIT
{
    int f[3*N];

    void upd(int id)
    {
        for(; id > 0; id -= id & -id) f[id] += 1;
    }

    int get(int id)
    {
        int ans = 0;
        for(; id<3*N; id += id & -id) ans += f[id];
        return ans;
    }
} pos;

void solve()
{
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) 
    {
        cin >> a[i].fi >> a[i].se;
        rar.eb(a[i].fi);
        rar.eb(a[i].se);
    }

    for(int i = 1; i <= k; ++i)
    {
        cin >> t[i].fi; t[i].se = i;
        rar.eb(t[i].fi);
    }

    sort(rar.begin(), rar.end());
    rar.erase(unique(rar.begin(), rar.end()), rar.end());

    for(int i = 1; i <= k; ++i)
    {
        t[i].fi = upper_bound(rar.begin(), rar.end(), t[i].fi) - rar.begin();
        tree.upd(t[i].fi, i);
    }

    sort(t+1, t+1+k, [] (ii x, ii y) {return x.fi < y.fi;});
    sort(a+1, a+1+n, [] (ii x, ii y) {return max(x.fi, x.se) > max(y.fi, y.se);});

    int id = k;
    ll tot = 0;

    for(int i = 1; i <= n; ++i)
    {
        a[i].fi = upper_bound(rar.begin(), rar.end(), a[i].fi) - rar.begin();
        a[i].se = upper_bound(rar.begin(), rar.end(), a[i].se) - rar.begin();

        int x = min(a[i].fi, a[i].se), y = max(a[i].fi, a[i].se);
        while(t[id].fi >= y and id > 0)
        {
            pos.upd(t[id].se);
            id--;
        }

        int last = tree.get(x, y-1);
        int tmp = pos.get(last);

        tot += (tmp & 1) ? rar[a[i].se-1] : rar[a[i].fi-1];
    }       

    cout << tot;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

fortune_telling2.cpp: In function 'int32_t main()':
fortune_telling2.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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