oj.uz

Submission #964897

# Submission time Handle Problem Language Result Execution time Memory
964897 2024-04-17T17:06:36 Z Ahmed57 Teams (IOI15_teams) C++17
77 / 100
 861 ms 154104 KB 
#include "bits/stdc++.h"
using namespace std;
int NODES = 0;
int L[30000001],R[30000001],ST[30000001];
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 6592 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 2 ms 6744 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 2 ms 6500 KB Output is correct
13 Correct 2 ms 6492 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 1 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 2 ms 6492 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Correct 2 ms 6584 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 6588 KB Output is correct
26 Correct 2 ms 6488 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 31944 KB Output is correct
2 Correct 48 ms 31968 KB Output is correct
3 Correct 44 ms 32056 KB Output is correct
4 Correct 58 ms 34212 KB Output is correct
5 Correct 23 ms 31800 KB Output is correct
6 Correct 23 ms 31616 KB Output is correct
7 Correct 23 ms 31604 KB Output is correct
8 Correct 24 ms 31652 KB Output is correct
9 Correct 31 ms 30244 KB Output is correct
10 Correct 27 ms 29640 KB Output is correct
11 Correct 21 ms 31424 KB Output is correct
12 Correct 23 ms 29560 KB Output is correct
13 Correct 28 ms 31940 KB Output is correct
14 Correct 30 ms 29800 KB Output is correct
15 Correct 40 ms 32132 KB Output is correct
16 Correct 37 ms 31948 KB Output is correct
17 Correct 28 ms 32096 KB Output is correct
18 Correct 27 ms 31944 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 32756 KB Output is correct
2 Correct 105 ms 32708 KB Output is correct
3 Correct 174 ms 35832 KB Output is correct
4 Correct 60 ms 34092 KB Output is correct
5 Correct 100 ms 32364 KB Output is correct
6 Correct 97 ms 32276 KB Output is correct
7 Correct 119 ms 32308 KB Output is correct
8 Correct 102 ms 32444 KB Output is correct
9 Correct 31 ms 30416 KB Output is correct
10 Correct 91 ms 30196 KB Output is correct
11 Correct 66 ms 32032 KB Output is correct
12 Correct 108 ms 30148 KB Output is correct
13 Correct 180 ms 32720 KB Output is correct
14 Correct 210 ms 34288 KB Output is correct
15 Correct 166 ms 32844 KB Output is correct
16 Correct 183 ms 32748 KB Output is correct
17 Correct 161 ms 32680 KB Output is correct
18 Correct 190 ms 32544 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 146764 KB Output is correct
2 Correct 543 ms 146760 KB Output is correct
3 Correct 825 ms 154104 KB Output is correct
4 Correct 395 ms 150544 KB Output is correct
5 Correct 322 ms 145168 KB Output is correct
6 Correct 310 ms 145256 KB Output is correct
7 Correct 335 ms 145196 KB Output is correct
8 Correct 306 ms 145336 KB Output is correct
9 Correct 188 ms 142524 KB Output is correct
10 Correct 191 ms 144208 KB Output is correct
11 Correct 211 ms 144464 KB Output is correct
12 Correct 330 ms 148980 KB Output is correct
13 Correct 825 ms 150632 KB Output is correct
14 Correct 861 ms 152652 KB Output is correct
15 Correct 588 ms 148928 KB Output is correct
16 Correct 571 ms 148656 KB Output is correct
17 Correct 465 ms 148236 KB Output is correct
18 Incorrect 488 ms 148212 KB Output isn't correct
19 Halted 0 ms 0 KB -