oj.uz

Submission #1010148

# Submission time Handle Problem Language Result Execution time Memory
1010148 2024-06-28T11:25:06 Z hotboy2703 Teams (IOI15_teams) C++17
100 / 100
 1117 ms 366004 KB 
#include "teams.h"

#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXM = 5e5;
struct node{
    node *l,*r;
    ll lazy;
};
void build(node *cur,ll l,ll r){
    cur->lazy=0;
    if (l!=r){
        ll mid = (l + r) >> 1;
        cur->l=new node;
        cur->r=new node;
        build(cur->l,l,mid);
        build(cur->r,mid+1,r);
    }
}
node* update(node* cur,ll l,ll r,ll i){
    if (l > i || r < i)return cur;
    if (l == r){
        node* res = new node;
        res->lazy=cur->lazy+1;
        res->l=cur->l;
        res->r=cur->r;
        return res;
    }
    ll mid = (l + r) >> 1;
    node *res = new node;
    res->l = update(cur->l,l,mid,i);
    res->r = update(cur->r,mid+1,r,i);
    res->lazy=res->l->lazy+res->r->lazy;
    return res;
}
node* update(node* cur,ll i){
//    cout<<"UPDATE "<<l<<' '<<r<<' '<<val<<endl;
    return update(cur,0,MAXM,i);
}
ll get(node* cur,ll l,ll r,ll l1,ll r1){
    if (l > r1 || l1 > r || l1 > r1)return 0;
    if (l1 <= l && r <= r1)return cur->lazy;
    ll mid = (l + r) >> 1;
    return get(cur->l,l,mid,l1,r1)+get(cur->r,mid+1,r,l1,r1);
}
ll get(node* cur,ll l,ll r){
    return get(cur,0,MAXM,l,r);
}

node *tree[MAXM+100];
ll query(ll l,ll r){
    return get(tree[r],l+1,r);
}
vector <pll> a;
ll n;
void init(int N, int A[], int B[]) {
    n=N;
    for (ll i = 0;i < n;i ++){
        a.push_back({B[i],A[i]});
    }
    sort(a.begin(),a.end(),greater <> ());
    tree[MAXM+1]=new node;
    build(tree[MAXM+1],0,MAXM);
    for (ll i = MAXM,ptr = 0;i >= 1;i --){
        tree[i] = tree[i+1];
        while (ptr < sz(a) && a[ptr].fi >= i){
            tree[i] = update(tree[i],a[ptr].se);
            ptr++;
        }
    }
}
ll b[MAXM+100];
ll m;
int can(int M, int K[]) {
//    if (n > 100000)return 0;
    m=M;
    ll sum = 0;
    for (ll i = 0;i < m;i ++){b[i] = K[i];sum += b[i];}
    if (sum > n)return 0;
    sort(b,b+m);
    vector <pll> c;
    for (ll i =0 ;i < m;i ++){
        if (sz(c)!=0&&c.back().fi==b[i]){
            c.back().se++;
        }
        else{
            c.push_back(MP(b[i],1));
        }
    }
    vector <ll> dp(sz(c));
    set <ll> s;
    set <pll> del;
    for (ll i = 0;i < sz(c);i ++){
        auto add_del=[&](set <ll> :: iterator tmp)->void{
            if (tmp==s.begin())return;
            ll x = *(prev(tmp));
            ll l = i;
            ll r = sz(c)-1;
            while (l <= r){
                ll mid = (l + r) >> 1;
                if (dp[x] - query(c[x].fi,c[mid].fi) > dp[*tmp] - query(c[*tmp].fi,c[mid].fi)){
                    r = mid - 1;
                }
                else{
                    l = mid + 1;
                }
            }
            del.insert(MP(l,*tmp));
        };
        if (i){
            auto tmp = s.insert(i-1);
            add_del(tmp.fi);
        }
        while (sz(del) && (*(del.begin())).fi == i){
            auto x = s.find((*(del.begin())).se);
            del.erase(del.begin());
            if (x==s.end())continue;
            auto tmp=s.erase(x);

            if (tmp!=s.end()){
                add_del(tmp);
            }
        }
        dp[i] = c[i].fi*c[i].se-query(0,c[i].fi);
        if (sz(s)){
            ll j = *(s.rbegin());
            dp[i] = max(dp[i],dp[j] + c[i].fi*c[i].se-query(c[j].fi,c[i].fi));
        }
        if (dp[i] > 0)return 0;
    }
	return 1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37208 KB Output is correct
2 Correct 24 ms 37208 KB Output is correct
3 Correct 39 ms 37400 KB Output is correct
4 Correct 27 ms 37468 KB Output is correct
5 Correct 27 ms 37408 KB Output is correct
6 Correct 30 ms 37476 KB Output is correct
7 Correct 45 ms 37460 KB Output is correct
8 Correct 24 ms 37468 KB Output is correct
9 Correct 26 ms 37256 KB Output is correct
10 Correct 26 ms 37464 KB Output is correct
11 Correct 40 ms 37456 KB Output is correct
12 Correct 29 ms 37456 KB Output is correct
13 Correct 28 ms 37468 KB Output is correct
14 Correct 32 ms 37460 KB Output is correct
15 Correct 29 ms 37464 KB Output is correct
16 Correct 28 ms 37460 KB Output is correct
17 Correct 46 ms 37204 KB Output is correct
18 Correct 28 ms 37204 KB Output is correct
19 Correct 27 ms 37468 KB Output is correct
20 Correct 28 ms 37468 KB Output is correct
21 Correct 26 ms 37384 KB Output is correct
22 Correct 26 ms 37200 KB Output is correct
23 Correct 30 ms 37468 KB Output is correct
24 Correct 25 ms 37204 KB Output is correct
25 Correct 27 ms 37412 KB Output is correct
26 Correct 27 ms 37288 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 101320 KB Output is correct
2 Correct 126 ms 101320 KB Output is correct
3 Correct 128 ms 101316 KB Output is correct
4 Correct 147 ms 101828 KB Output is correct
5 Correct 87 ms 101436 KB Output is correct
6 Correct 124 ms 101328 KB Output is correct
7 Correct 95 ms 101316 KB Output is correct
8 Correct 101 ms 101368 KB Output is correct
9 Correct 98 ms 101828 KB Output is correct
10 Correct 99 ms 101780 KB Output is correct
11 Correct 113 ms 101572 KB Output is correct
12 Correct 91 ms 101572 KB Output is correct
13 Correct 113 ms 101320 KB Output is correct
14 Correct 104 ms 101484 KB Output is correct
15 Correct 152 ms 101420 KB Output is correct
16 Correct 119 ms 101508 KB Output is correct
17 Correct 100 ms 101840 KB Output is correct
18 Correct 97 ms 101396 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 101832 KB Output is correct
2 Correct 141 ms 101836 KB Output is correct
3 Correct 273 ms 104576 KB Output is correct
4 Correct 121 ms 102008 KB Output is correct
5 Correct 325 ms 101728 KB Output is correct
6 Correct 401 ms 101828 KB Output is correct
7 Correct 105 ms 101824 KB Output is correct
8 Correct 264 ms 101884 KB Output is correct
9 Correct 93 ms 101816 KB Output is correct
10 Correct 115 ms 102104 KB Output is correct
11 Correct 108 ms 101832 KB Output is correct
12 Correct 298 ms 102088 KB Output is correct
13 Correct 271 ms 101828 KB Output is correct
14 Correct 229 ms 103412 KB Output is correct
15 Correct 202 ms 102024 KB Output is correct
16 Correct 197 ms 103332 KB Output is correct
17 Correct 266 ms 102340 KB Output is correct
18 Correct 177 ms 101828 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 729 ms 358332 KB Output is correct
2 Correct 621 ms 358352 KB Output is correct
3 Correct 925 ms 364268 KB Output is correct
4 Correct 588 ms 358660 KB Output is correct
5 Correct 885 ms 358500 KB Output is correct
6 Correct 907 ms 358328 KB Output is correct
7 Correct 377 ms 358396 KB Output is correct
8 Correct 824 ms 358412 KB Output is correct
9 Correct 406 ms 359096 KB Output is correct
10 Correct 426 ms 359252 KB Output is correct
11 Correct 473 ms 359096 KB Output is correct
12 Correct 971 ms 359216 KB Output is correct
13 Correct 857 ms 358884 KB Output is correct
14 Correct 1117 ms 361528 KB Output is correct
15 Correct 767 ms 359696 KB Output is correct
16 Correct 755 ms 366004 KB Output is correct
17 Correct 716 ms 364852 KB Output is correct
18 Correct 548 ms 364988 KB Output is correct