oj.uz

Submission #964903

# Submission time Handle Problem Language Result Execution time Memory
964903 2024-04-17T17:08:58 Z Ahmed57 Teams (IOI15_teams) C++17
77 / 100
 996 ms 154672 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 = (x==3?x+1: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 6492 KB Output is correct
3 Correct 2 ms 6592 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 7000 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 1 ms 6596 KB Output is correct
9 Correct 2 ms 6748 KB Output is correct
10 Correct 2 ms 6604 KB Output is correct
11 Correct 1 ms 6492 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 6644 KB Output is correct
15 Correct 2 ms 6748 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6740 KB Output is correct
19 Correct 1 ms 6588 KB Output is correct
20 Correct 2 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 1 ms 6584 KB Output is correct
23 Correct 2 ms 6744 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 2 ms 6488 KB Output is correct
26 Correct 1 ms 6492 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 31908 KB Output is correct
2 Correct 47 ms 31708 KB Output is correct
3 Correct 42 ms 29828 KB Output is correct
4 Correct 65 ms 34464 KB Output is correct
5 Correct 28 ms 31696 KB Output is correct
6 Correct 26 ms 31592 KB Output is correct
7 Correct 25 ms 31800 KB Output is correct
8 Correct 23 ms 31592 KB Output is correct
9 Correct 32 ms 32296 KB Output is correct
10 Correct 35 ms 31760 KB Output is correct
11 Correct 20 ms 33488 KB Output is correct
12 Correct 20 ms 31540 KB Output is correct
13 Correct 27 ms 33992 KB Output is correct
14 Correct 30 ms 30492 KB Output is correct
15 Correct 42 ms 30604 KB Output is correct
16 Correct 50 ms 32104 KB Output is correct
17 Correct 28 ms 34148 KB Output is correct
18 Correct 24 ms 30872 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 32672 KB Output is correct
2 Correct 102 ms 32676 KB Output is correct
3 Correct 179 ms 36072 KB Output is correct
4 Correct 69 ms 34320 KB Output is correct
5 Correct 119 ms 32288 KB Output is correct
6 Correct 95 ms 32292 KB Output is correct
7 Correct 103 ms 32288 KB Output is correct
8 Correct 121 ms 32436 KB Output is correct
9 Correct 32 ms 32388 KB Output is correct
10 Correct 75 ms 32220 KB Output is correct
11 Correct 82 ms 34220 KB Output is correct
12 Correct 113 ms 27316 KB Output is correct
13 Correct 221 ms 34736 KB Output is correct
14 Correct 225 ms 34600 KB Output is correct
15 Correct 170 ms 32676 KB Output is correct
16 Correct 185 ms 32620 KB Output is correct
17 Correct 161 ms 34776 KB Output is correct
18 Correct 206 ms 34800 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 148024 KB Output is correct
2 Correct 585 ms 150700 KB Output is correct
3 Correct 931 ms 154672 KB Output is correct
4 Correct 469 ms 151824 KB Output is correct
5 Correct 302 ms 146264 KB Output is correct
6 Correct 303 ms 146192 KB Output is correct
7 Correct 312 ms 146116 KB Output is correct
8 Correct 316 ms 146116 KB Output is correct
9 Correct 202 ms 143472 KB Output is correct
10 Correct 225 ms 145144 KB Output is correct
11 Correct 230 ms 145520 KB Output is correct
12 Correct 369 ms 146256 KB Output is correct
13 Correct 969 ms 148044 KB Output is correct
14 Correct 996 ms 151736 KB Output is correct
15 Correct 671 ms 149008 KB Output is correct
16 Correct 690 ms 148996 KB Output is correct
17 Correct 551 ms 146512 KB Output is correct
18 Incorrect 561 ms 148396 KB Output isn't correct
19 Halted 0 ms 0 KB -