Submission #1212940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212940		Lemser	Teams (IOI15_teams)	C++20	21 / 100	4104 ms	589824 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
 
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }

struct SegTree{
    SegTree *left, *right;
    ll l, r, s=0;
    SegTree () {  }
    SegTree (ll l, ll r): l(l), r(r) {  }

    void build(){
        if(l==r) s=0;
        else{
            ll mid = (l+r)/2;
            left = new SegTree(l, mid);
            right = new SegTree(mid+1, r);
            left->build();right->build();
        }
    }

    SegTree *update(ll i, ll v){
        if(r<i || l>i)return this;
        SegTree *t = new SegTree(l, r);
        if(l==r) t->s = s+v;
        else{
            t->left=left->update(i, v);
            t->right=right->update(i,v);
            t->s = t->left->s + t->right->s;
        }
        return t;
    }

    ll query (ll i, ll j){
        if (l>j || r<i) return 0;
        if (l>=i && r<=j) return s;
        return right->query(i, j)+left->query(i,j);
    }
};

const int N = 5e5 + 7;
SegTree *st[N];
vll ps[N];
ll n;

void init(int N, int a[], int b[]) {
	n = N;
	st[0] = new SegTree(0, n);
	st[0]->build();
	fo (i, n) ps[a[i]].pb(b[i]);
	fore  (x, 1, n+1) {
		st[x] = st[x-1]->update(0, 0);
		for (ll y: ps[x]) {
			st[x] = st[x]->update(y, +1);
		}
	}
}

ll rectangles (ll x1, ll x2, ll y1, ll y2) {
	ll ans = st[x2]->query(y1, y2);
	if (x1 > 0) ans -= st[x1-1]->query(y1, y2);
	return ans;
}

ll isec (ll k1, ll k2) {
	assert(k1 <= k2);
	if (k1 == k2) return 0ll;
	return rectangles (k1+1, k2, k2, n);
}

int can(int m, int k[]) {
	sort(k, k+m);
	vll dp(m, 0);
	fo (i, m) {
		// no elegir a nadie
		dp[i] = rectangles(0, k[i], k[i], n) - k[i];
		fo (j, i) {
			dp[i] = min(dp[i], dp[j] + isec(k[j], k[i]) - k[i]);
		}
		if (dp[i] < 0) return 0;
	}
	return 1;
}

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