oj.uz

Submission #964894

# Submission time Handle Problem Language Result Execution time Memory
964894 2024-04-17T17:05:26 Z Ahmed57 Teams (IOI15_teams) C++17
77 / 100
 861 ms 152908 KB 
#include "bits/stdc++.h"
using namespace std;
int NODES = 0;
int L[20000001],R[20000001],ST[20000001];
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 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 2 ms 6488 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 2 ms 6544 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 1 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 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6488 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 2 ms 6492 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 28840 KB Output is correct
2 Correct 38 ms 28892 KB Output is correct
3 Correct 40 ms 29172 KB Output is correct
4 Correct 53 ms 30928 KB Output is correct
5 Correct 22 ms 28876 KB Output is correct
6 Correct 24 ms 28880 KB Output is correct
7 Correct 22 ms 28880 KB Output is correct
8 Correct 22 ms 28984 KB Output is correct
9 Correct 32 ms 29648 KB Output is correct
10 Correct 24 ms 29136 KB Output is correct
11 Correct 17 ms 29000 KB Output is correct
12 Correct 22 ms 28880 KB Output is correct
13 Correct 25 ms 28724 KB Output is correct
14 Correct 25 ms 28868 KB Output is correct
15 Correct 35 ms 28984 KB Output is correct
16 Correct 34 ms 28732 KB Output is correct
17 Correct 23 ms 28880 KB Output is correct
18 Correct 22 ms 28880 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 29244 KB Output is correct
2 Correct 103 ms 29232 KB Output is correct
3 Correct 151 ms 31944 KB Output is correct
4 Correct 57 ms 30716 KB Output is correct
5 Correct 108 ms 29100 KB Output is correct
6 Correct 88 ms 29248 KB Output is correct
7 Correct 97 ms 29124 KB Output is correct
8 Correct 96 ms 29028 KB Output is correct
9 Correct 32 ms 29644 KB Output is correct
10 Correct 65 ms 29408 KB Output is correct
11 Correct 68 ms 29132 KB Output is correct
12 Correct 96 ms 29168 KB Output is correct
13 Correct 200 ms 29240 KB Output is correct
14 Correct 203 ms 30656 KB Output is correct
15 Correct 152 ms 29288 KB Output is correct
16 Correct 153 ms 29140 KB Output is correct
17 Correct 182 ms 29216 KB Output is correct
18 Correct 192 ms 29192 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 142516 KB Output is correct
2 Correct 476 ms 142464 KB Output is correct
3 Correct 722 ms 148320 KB Output is correct
4 Correct 397 ms 152908 KB Output is correct
5 Correct 280 ms 147376 KB Output is correct
6 Correct 290 ms 147128 KB Output is correct
7 Correct 290 ms 147224 KB Output is correct
8 Correct 281 ms 147408 KB Output is correct
9 Correct 193 ms 146056 KB Output is correct
10 Correct 183 ms 145888 KB Output is correct
11 Correct 202 ms 146268 KB Output is correct
12 Correct 300 ms 147020 KB Output is correct
13 Correct 834 ms 148976 KB Output is correct
14 Correct 861 ms 151468 KB Output is correct
15 Correct 608 ms 147472 KB Output is correct
16 Correct 594 ms 148168 KB Output is correct
17 Correct 479 ms 149088 KB Output is correct
18 Incorrect 494 ms 149256 KB Output isn't correct
19 Halted 0 ms 0 KB -