oj.uz

Submission #964911

# Submission time Handle Problem Language Result Execution time Memory
964911 2024-04-17T17:15:32 Z Ahmed57 Teams (IOI15_teams) C++17
100 / 100
 836 ms 155752 KB 
#include "bits/stdc++.h"
using namespace std;
int NODES = 0;
int L[50000001],R[50000001],ST[50000001];
int newleaf(int val){
    NODES++;
    L[NODES] = -1;
    R[NODES] = -1;
    ST[NODES] = val;
    return NODES;
}
int newparent(int l,int r){
    NODES++;
    L[NODES] = l;
    R[NODES] = r;
    ST[NODES] = ST[l]+ST[r];
    return NODES;
}
int build(int l,int r){
    if(l==r)return newleaf(0);
    int md = (l+r)/2;
    return newparent(build(l,md),build(md+1,r));
}
int update(int p,int l,int r,int idx){
    if(l==r)return newleaf(1+ST[p]);
    int md = (l+r)/2;
    if(idx<=md)return newparent(update(L[p],l,md,idx),R[p]);
    else return newparent(L[p],update(R[p],md+1,r,idx));
}
int query(int p1,int p2,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq){
        return ST[p2]-ST[p1];
    }
    if(r<lq||l>rq)return 0;
    int md = (l+r)/2;
    return query(L[p1],L[p2],l,md,lq,rq)+query(R[p1],R[p2],md+1,r,lq,rq);
}
int root[500001],n;
vector<pair<int,int>> v;
void init(int N,int A[],int B[]){
    n = N;
    for(int i = 0;i<N;i++){
        v.push_back({A[i],B[i]});
    }
    sort(v.begin(),v.end());
    root[0] = build(1,n);
    for(int i = 1;i<=v.size();i++){
        root[i] = update(root[i-1],1,n,v[i-1].second);
    }
}
int w(int a,int b){
    int it = lower_bound(v.begin(),v.end(),make_pair(a+1,0))-v.begin();
    int it2 = lower_bound(v.begin(),v.end(),make_pair(b+1,0))-v.begin();
    return query(root[it],root[it2],1,n,b,n);
}
bool can(int m,int k[]){
    vector<int> K;
    K.push_back(0);
    for(int i = 0;i<m;i++){
        K.push_back(k[i]);
    }
    sort(K.begin(),K.end());
    long long dp[m+1]; dp[0] =0;
    deque<pair<long long,long long> > v; // start pos, best-k
    v.push_back(make_pair(0LL,0LL));
    for (int x=1; x <= m; x++) {
        int lol = (--lower_bound(v.begin(), v.end(), make_pair((long long)x+1, 0LL)))->second;
        dp[x] = dp[lol] + w(K[lol], K[x]) - K[x];
        while(v.size()){
            int y = (v.size()==1?m:v[1].first-1), oldk = v[0].second;
            if (y <= x || (y > x && dp[x] + w(K[x], K[y]) - K[y] <= dp[oldk] + w(K[oldk], K[y]) - K[y]))
                v.pop_front();
            else {
                //cerr<<x<<endl;
                int lo = max(x+1,(int)v[0].first), hi = m , ans = m+1;
                while(lo <= hi) {
                    int mid = (lo+hi)/2;
                    //cout<<mid<<endl;
                    if (dp[x] + w(K[x], K[mid]) - K[mid] <= dp[oldk] + w(K[oldk], K[mid]) - K[mid]){
                        lo = mid+1;
                        ans = mid;
                    }else hi = mid-1;
                }
                if (ans != m+1){
                    v[0].first = ans+1;
                    v.push_front(make_pair(x+1, x));
                }else{
                    if(v[0].first>x+1){
                        v.push_front(make_pair(x+1, x));
                    }
                }
                break;
            }
        }
        if (v.size() == 0)
            v.push_back(make_pair(x+1LL, x));
    }
    for(int i = 1;i<=m;i++){
        if(dp[i]<0)return 0;
    }
    return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i = 1;i<=v.size();i++){
      |                   ~^~~~~~~~~~
teams.cpp: In function 'int w(int, int)':
teams.cpp:52:61: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   52 |     int it = lower_bound(v.begin(),v.end(),make_pair(a+1,0))-v.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
teams.cpp:53:62: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   53 |     int it2 = lower_bound(v.begin(),v.end(),make_pair(b+1,0))-v.begin();
      |               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
teams.cpp: In function 'bool can(int, int*)':
teams.cpp:64:39: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   64 |     deque<pair<long long,long long> > v; // start pos, best-k
      |                                       ^
teams.cpp:39:23: note: shadowed declaration is here
   39 | vector<pair<int,int>> v;
      |                       ^
teams.cpp:67:88: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   67 |         int lol = (--lower_bound(v.begin(), v.end(), make_pair((long long)x+1, 0LL)))->second;
      |                   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
teams.cpp:70:33: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |             int y = (v.size()==1?m:v[1].first-1), oldk = v[0].second;
      |                     ~~~~~~~~~~~~^~~~~~~~~~~~~~~~
teams.cpp:70:63: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   70 |             int y = (v.size()==1?m:v[1].first-1), oldk = v[0].second;

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6500 KB Output is correct
3 Correct 2 ms 6584 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6580 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6560 KB Output is correct
12 Correct 2 ms 6492 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 1 ms 6584 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6584 KB Output is correct
20 Correct 2 ms 6488 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6492 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 1 ms 6600 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 32112 KB Output is correct
2 Correct 41 ms 31944 KB Output is correct
3 Correct 39 ms 31972 KB Output is correct
4 Correct 59 ms 34200 KB Output is correct
5 Correct 22 ms 31784 KB Output is correct
6 Correct 22 ms 31696 KB Output is correct
7 Correct 22 ms 31780 KB Output is correct
8 Correct 22 ms 31768 KB Output is correct
9 Correct 35 ms 32300 KB Output is correct
10 Correct 24 ms 31692 KB Output is correct
11 Correct 22 ms 33476 KB Output is correct
12 Correct 18 ms 31468 KB Output is correct
13 Correct 29 ms 33888 KB Output is correct
14 Correct 26 ms 31948 KB Output is correct
15 Correct 41 ms 32048 KB Output is correct
16 Correct 37 ms 32136 KB Output is correct
17 Correct 23 ms 34104 KB Output is correct
18 Correct 26 ms 33992 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 32712 KB Output is correct
2 Correct 104 ms 32648 KB Output is correct
3 Correct 133 ms 36116 KB Output is correct
4 Correct 55 ms 34324 KB Output is correct
5 Correct 92 ms 32372 KB Output is correct
6 Correct 99 ms 32652 KB Output is correct
7 Correct 104 ms 32276 KB Output is correct
8 Correct 103 ms 32420 KB Output is correct
9 Correct 31 ms 32448 KB Output is correct
10 Correct 57 ms 32196 KB Output is correct
11 Correct 62 ms 34212 KB Output is correct
12 Correct 93 ms 32312 KB Output is correct
13 Correct 203 ms 34760 KB Output is correct
14 Correct 182 ms 34616 KB Output is correct
15 Correct 164 ms 32712 KB Output is correct
16 Correct 176 ms 32816 KB Output is correct
17 Correct 166 ms 34760 KB Output is correct
18 Correct 187 ms 34792 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 149024 KB Output is correct
2 Correct 517 ms 149020 KB Output is correct
3 Correct 797 ms 155752 KB Output is correct
4 Correct 439 ms 151900 KB Output is correct
5 Correct 301 ms 146244 KB Output is correct
6 Correct 296 ms 146108 KB Output is correct
7 Correct 311 ms 146108 KB Output is correct
8 Correct 305 ms 146084 KB Output is correct
9 Correct 190 ms 143508 KB Output is correct
10 Correct 195 ms 145192 KB Output is correct
11 Correct 223 ms 145428 KB Output is correct
12 Correct 316 ms 146360 KB Output is correct
13 Correct 758 ms 148024 KB Output is correct
14 Correct 836 ms 151708 KB Output is correct
15 Correct 605 ms 148980 KB Output is correct
16 Correct 611 ms 148908 KB Output is correct
17 Correct 508 ms 148696 KB Output is correct
18 Correct 489 ms 148436 KB Output is correct