Submission #336739

#	Time	Username	Problem	Language	Result	Execution time	Memory
336739		12tqian	Teams (IOI15_teams)	C++17	77 / 100	1309 ms	233964 KiB

teams

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<db, db> pd;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<db> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int) (x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(all(x))
#define rsz resize
#define resz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define f1r(i, a, b) for (int i = (a); i < (b); ++i)
#define f0r(i, a) f1r(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto& a : x)

const int LIM = 5e6;
#include "teams.h"
struct Node {
    int lc, rc, sum;
} t[LIM];
int nodes = 0;
int modify(int p, int x, int v, int l, int r) {
    int u = ++nodes;
    if (l == r) {
        t[u].sum = t[p].sum +  v;
    } else {
        int m = (l+r)/2;
        if (x <= m) {
            t[u].lc = modify(t[p].lc, x, v, l, m);
            t[u].rc = t[p].rc;
        } else {
            t[u].lc = t[p].lc;
            t[u].rc = modify(t[p].rc, x, v, m+1, r);
        }
        t[u].sum = t[t[u].lc].sum+t[t[u].rc].sum;
    }
    return u;
}
int query(int p, int lo, int hi, int l, int r) {
    if (lo > hi) return 0;
    if (hi < l || r < lo) return 0;
    if (lo <= l && r <= hi) return t[p].sum;
    int m = (l+r)/2;
    return query(t[p].lc, lo, hi, l, m) + query(t[p].rc, lo, hi, m+1, r);
}
int n; 
vi a;
vi b;
vector<vpi> ri;
vector<vpi> le;
vi ti(n);

void init(int N, int A[], int B[]) {
    n = N;
    a.resize(n);
    b.resize(n);
    ri.resize(n+5);
    le.resize(n+5);
    ti.resize(n+5);

    f0r(i, n) a[i] = A[i], b[i] = B[i];
    f0r(i, n) ri[b[i]].eb(a[i], i);
    f0r(i, n) le[a[i]].eb(b[i], i);

    int cur_time = 0;
    f1r(i, 1, n+1) {
        for (auto& x : le[i]) {
            cur_time = modify(cur_time, x.f, 1, 1, n);
        }
        ti[i] = cur_time;
    }
}   

int can(int M, int K[]) {
    int m = M;
    vi k(m);
    f0r(i, m) k[i] = K[i];
    sort(all(k));
    vpi pv;
    f0r(i, m) {
        if (sz(pv) == 0 || pv.back().f != k[i]) {
            pv.eb(k[i], k[i]);
        } else {
            pv.back().s += k[i];
        }
    }
    int sz = sz(pv);
    vpi gap;
    f0r(i, sz) {
        if (i == 0) {
            gap.eb(1, pv[i].f-1);
        } else {
            gap.eb(pv[i-1].f, pv[i].f-1);
        }
        if (i == sz-1) {
            gap.eb(pv[i].f, n);
        }
    }
    int num = sz(gap);
    vi taken(num);
    
    f0r(i, sz) {
        int need = pv[i].s;
        int val = pv[i].f;
        f0r(i, num) {
            auto& x = gap[i];
            if (x.f < val) continue;
            int rem = query(ti[val], x.f, x.s, 1, n);
            rem -= taken[i];
            if (rem >= need) {
                taken[i] += need;
                need = 0;
            } else {
                need -= rem;
                taken[i] += rem;
            }
            if (need == 0) break;
        }
        if (need) return 0;
    }
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:167:13: warning: declaration of 'i' shadows a previous local [-Wshadow]
  167 |         f0r(i, num) {
      |             ^
teams.cpp:70:31: note: in definition of macro 'f1r'
   70 | #define f1r(i, a, b) for (int i = (a); i < (b); ++i)
      |                               ^
teams.cpp:167:9: note: in expansion of macro 'f0r'
  167 |         f0r(i, num) {
      |         ^~~
teams.cpp:164:9: note: shadowed declaration is here
  164 |     f0r(i, sz) {
      |         ^
teams.cpp:70:31: note: in definition of macro 'f1r'
   70 | #define f1r(i, a, b) for (int i = (a); i < (b); ++i)
      |                               ^
teams.cpp:164:5: note: in expansion of macro 'f0r'
  164 |     f0r(i, sz) {
      |     ^~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23