oj.uz

Submission #1010018

# Submission time Handle Problem Language Result Execution time Memory
1010018 2024-06-28T09:11:49 Z hotboy2703 Teams (IOI15_teams) C++17
100 / 100
 2253 ms 370848 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;
    for (ll i = 0;i < m;i ++)b[i] = K[i];
    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));
    for (ll i = 0;i < sz(c);i ++){
        dp[i] = c[i].fi*c[i].se-query(0,c[i].fi);
        for (ll j = i-1;j >= 0 && (i-j) <= 100;j --){
            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 25 ms 35412 KB Output is correct
2 Correct 27 ms 35476 KB Output is correct
3 Correct 27 ms 35668 KB Output is correct
4 Correct 42 ms 35684 KB Output is correct
5 Correct 27 ms 35676 KB Output is correct
6 Correct 27 ms 35676 KB Output is correct
7 Correct 28 ms 35640 KB Output is correct
8 Correct 27 ms 35676 KB Output is correct
9 Correct 31 ms 35668 KB Output is correct
10 Correct 27 ms 35552 KB Output is correct
11 Correct 43 ms 35668 KB Output is correct
12 Correct 28 ms 35664 KB Output is correct
13 Correct 40 ms 35664 KB Output is correct
14 Correct 28 ms 35676 KB Output is correct
15 Correct 28 ms 35672 KB Output is correct
16 Correct 27 ms 35668 KB Output is correct
17 Correct 28 ms 35428 KB Output is correct
18 Correct 28 ms 35676 KB Output is correct
19 Correct 38 ms 35516 KB Output is correct
20 Correct 31 ms 35664 KB Output is correct
21 Correct 27 ms 35676 KB Output is correct
22 Correct 26 ms 35676 KB Output is correct
23 Correct 27 ms 35552 KB Output is correct
24 Correct 27 ms 35664 KB Output is correct
25 Correct 27 ms 35664 KB Output is correct
26 Correct 28 ms 35668 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 100808 KB Output is correct
2 Correct 121 ms 100812 KB Output is correct
3 Correct 119 ms 100808 KB Output is correct
4 Correct 159 ms 101576 KB Output is correct
5 Correct 108 ms 100396 KB Output is correct
6 Correct 127 ms 100412 KB Output is correct
7 Correct 97 ms 100452 KB Output is correct
8 Correct 96 ms 100296 KB Output is correct
9 Correct 93 ms 100864 KB Output is correct
10 Correct 119 ms 100324 KB Output is correct
11 Correct 90 ms 100292 KB Output is correct
12 Correct 93 ms 100548 KB Output is correct
13 Correct 93 ms 100548 KB Output is correct
14 Correct 102 ms 100584 KB Output is correct
15 Correct 115 ms 100836 KB Output is correct
16 Correct 112 ms 100812 KB Output is correct
17 Correct 88 ms 100040 KB Output is correct
18 Correct 114 ms 99528 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 101600 KB Output is correct
2 Correct 115 ms 101600 KB Output is correct
3 Correct 211 ms 104904 KB Output is correct
4 Correct 122 ms 101768 KB Output is correct
5 Correct 986 ms 101028 KB Output is correct
6 Correct 852 ms 101196 KB Output is correct
7 Correct 122 ms 101060 KB Output is correct
8 Correct 682 ms 101064 KB Output is correct
9 Correct 90 ms 100812 KB Output is correct
10 Correct 90 ms 100804 KB Output is correct
11 Correct 126 ms 101064 KB Output is correct
12 Correct 824 ms 101320 KB Output is correct
13 Correct 278 ms 101572 KB Output is correct
14 Correct 202 ms 103312 KB Output is correct
15 Correct 175 ms 101568 KB Output is correct
16 Correct 180 ms 101624 KB Output is correct
17 Correct 171 ms 100548 KB Output is correct
18 Correct 161 ms 100120 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 363908 KB Output is correct
2 Correct 576 ms 363960 KB Output is correct
3 Correct 874 ms 370848 KB Output is correct
4 Correct 581 ms 364316 KB Output is correct
5 Correct 2253 ms 361288 KB Output is correct
6 Correct 2118 ms 361280 KB Output is correct
7 Correct 357 ms 361228 KB Output is correct
8 Correct 1696 ms 361148 KB Output is correct
9 Correct 344 ms 362424 KB Output is correct
10 Correct 315 ms 360376 KB Output is correct
11 Correct 755 ms 360908 KB Output is correct
12 Correct 2095 ms 361772 KB Output is correct
13 Correct 902 ms 363212 KB Output is correct
14 Correct 1000 ms 367568 KB Output is correct
15 Correct 698 ms 364232 KB Output is correct
16 Correct 659 ms 364232 KB Output is correct
17 Correct 542 ms 362940 KB Output is correct
18 Correct 521 ms 363096 KB Output is correct