oj.uz

Submission #964892

# Submission time Handle Problem Language Result Execution time Memory
964892 2024-04-17T17:03:04 Z Ahmed57 Teams (IOI15_teams) C++17
77 / 100
 838 ms 141064 KB 
#include "bits/stdc++.h"
using namespace std;
int NODES = 0;
int L[10000001],R[10000001],ST[10000001];
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[100001],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 2 ms 6492 KB Output is correct
4 Correct 2 ms 6740 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6608 KB Output is correct
7 Correct 1 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 2 ms 6492 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 1 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 1 ms 6488 KB Output is correct
18 Correct 1 ms 6748 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 6492 KB Output is correct
22 Correct 2 ms 6592 KB Output is correct
23 Correct 1 ms 6492 KB Output is correct
24 Correct 1 ms 6592 KB Output is correct
25 Correct 1 ms 6492 KB Output is correct
26 Correct 2 ms 6596 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 29892 KB Output is correct
2 Correct 38 ms 30140 KB Output is correct
3 Correct 46 ms 30100 KB Output is correct
4 Correct 53 ms 32196 KB Output is correct
5 Correct 22 ms 29640 KB Output is correct
6 Correct 22 ms 29780 KB Output is correct
7 Correct 23 ms 29620 KB Output is correct
8 Correct 22 ms 29648 KB Output is correct
9 Correct 33 ms 28204 KB Output is correct
10 Correct 28 ms 27600 KB Output is correct
11 Correct 22 ms 29388 KB Output is correct
12 Correct 18 ms 27440 KB Output is correct
13 Correct 25 ms 29736 KB Output is correct
14 Correct 25 ms 27800 KB Output is correct
15 Correct 35 ms 30000 KB Output is correct
16 Correct 50 ms 30152 KB Output is correct
17 Correct 23 ms 30220 KB Output is correct
18 Correct 29 ms 29892 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 30644 KB Output is correct
2 Correct 117 ms 30680 KB Output is correct
3 Correct 195 ms 33908 KB Output is correct
4 Correct 63 ms 32100 KB Output is correct
5 Correct 108 ms 30328 KB Output is correct
6 Correct 99 ms 30408 KB Output is correct
7 Correct 92 ms 30256 KB Output is correct
8 Correct 90 ms 30352 KB Output is correct
9 Correct 31 ms 28364 KB Output is correct
10 Correct 65 ms 28104 KB Output is correct
11 Correct 78 ms 29904 KB Output is correct
12 Correct 92 ms 28212 KB Output is correct
13 Correct 220 ms 30624 KB Output is correct
14 Correct 219 ms 30548 KB Output is correct
15 Correct 161 ms 30816 KB Output is correct
16 Correct 159 ms 30620 KB Output is correct
17 Correct 168 ms 30660 KB Output is correct
18 Correct 201 ms 30460 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 132952 KB Output is correct
2 Correct 517 ms 134240 KB Output is correct
3 Incorrect 838 ms 141064 KB Output isn't correct
4 Halted 0 ms 0 KB -