oj.uz

Submission #964900

# Submission time Handle Problem Language Result Execution time Memory
964900 2024-04-17T17:07:30 Z Ahmed57 Teams (IOI15_teams) C++17
77 / 100
 862 ms 150460 KB 
#include "bits/stdc++.h"
using namespace std;
int NODES = 0;
int L[40000001],R[40000001],ST[40000001];
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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6588 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6596 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 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 3 ms 6488 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 6492 KB Output is correct
17 Correct 2 ms 6500 KB Output is correct
18 Correct 2 ms 6744 KB Output is correct
19 Correct 1 ms 6496 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 1 ms 6592 KB Output is correct
22 Correct 1 ms 6492 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 2 ms 6492 KB Output is correct
25 Correct 1 ms 6492 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 46 ms 31744 KB Output is correct
2 Correct 40 ms 31772 KB Output is correct
3 Correct 39 ms 31688 KB Output is correct
4 Correct 55 ms 33844 KB Output is correct
5 Correct 26 ms 31812 KB Output is correct
6 Correct 22 ms 31716 KB Output is correct
7 Correct 23 ms 31812 KB Output is correct
8 Correct 22 ms 31580 KB Output is correct
9 Correct 32 ms 32376 KB Output is correct
10 Correct 24 ms 31812 KB Output is correct
11 Correct 18 ms 31552 KB Output is correct
12 Correct 18 ms 31528 KB Output is correct
13 Correct 25 ms 31796 KB Output is correct
14 Correct 27 ms 31580 KB Output is correct
15 Correct 38 ms 31784 KB Output is correct
16 Correct 35 ms 31688 KB Output is correct
17 Correct 26 ms 31692 KB Output is correct
18 Correct 23 ms 31752 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 32268 KB Output is correct
2 Correct 97 ms 32308 KB Output is correct
3 Correct 155 ms 35316 KB Output is correct
4 Correct 55 ms 33836 KB Output is correct
5 Correct 101 ms 32052 KB Output is correct
6 Correct 95 ms 31852 KB Output is correct
7 Correct 93 ms 31944 KB Output is correct
8 Correct 96 ms 32048 KB Output is correct
9 Correct 36 ms 32452 KB Output is correct
10 Correct 65 ms 32048 KB Output is correct
11 Correct 62 ms 31964 KB Output is correct
12 Correct 90 ms 31888 KB Output is correct
13 Correct 202 ms 32604 KB Output is correct
14 Correct 179 ms 33988 KB Output is correct
15 Correct 149 ms 32356 KB Output is correct
16 Correct 160 ms 32268 KB Output is correct
17 Correct 164 ms 32196 KB Output is correct
18 Correct 190 ms 32304 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 146888 KB Output is correct
2 Correct 512 ms 143576 KB Output is correct
3 Correct 765 ms 150460 KB Output is correct
4 Correct 400 ms 147900 KB Output is correct
5 Correct 316 ms 142800 KB Output is correct
6 Correct 280 ms 141776 KB Output is correct
7 Correct 288 ms 144636 KB Output is correct
8 Correct 282 ms 141564 KB Output is correct
9 Correct 175 ms 141280 KB Output is correct
10 Correct 193 ms 144816 KB Output is correct
11 Correct 214 ms 144812 KB Output is correct
12 Correct 277 ms 144568 KB Output is correct
13 Correct 763 ms 144828 KB Output is correct
14 Correct 862 ms 145608 KB Output is correct
15 Correct 552 ms 144796 KB Output is correct
16 Correct 596 ms 144592 KB Output is correct
17 Correct 474 ms 142880 KB Output is correct
18 Incorrect 481 ms 144764 KB Output isn't correct
19 Halted 0 ms 0 KB -