oj.uz

Submission #548405

# Submission time Handle Problem Language Result Execution time Memory
548405 2022-04-13T09:23:01 Z neki Jousting tournament (IOI12_tournament) C++14
100 / 100
 82 ms 19172 KB 
#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define par pair<ll, ll>
#define ld long double
#define mod 998244353

struct segtr{
    ll n;
    vc<ll> sum;
    
    void build(ll l, ll r, ll no=1){
        if(l+1==r) sum[no]=1;
        else{
            ll mid=(l+r)/2;
            build(l, mid, 2 * no);
            build(mid, r, 2 * no + 1);
            sum[no] = sum[2 * no] + sum[2 * no + 1];
        }
    }
    segtr(ll n_){
        n=n_;
        sum.resize(4 * n);
        build(0, n);
    }
    ll findkth(ll kth, ll add, ll l, ll r, ll no=1){
        if(l+1==r){ 
            sum[no]+=add;
            return l;
        }
        else{
            ll mid=(l+r)/2, ret;
            if(kth<=sum[2 * no]) ret=findkth(kth, add, l, mid, no * 2);
            else ret=findkth(kth-sum[2 * no], add, mid, r, no * 2 +1);
            
            sum[no] = sum[2 * no] + sum[2 * no + 1];
            return ret;
        }
    }
};

int GetBestPosition(int n, int c, int r, int *k, int *s, int *e){
    segtr sg(n);
    
    vc<vc<ll>> tredg(n);
    
    vc<ll> kdo(n); 
    vc<ll> dp(n, 0), vseb(n, r), po(n), best(n);
    
    loop(i, 0, n){
        kdo[i]=i;
        if(i<n-1)po[i]=k[i];
        else po[i]=0;
        best[i]=i;
    }
    
    loop(i, 0, c){
        // ustvari novga
        ll nov=dp.size();
        dp.ps(0); vseb.ps(r);po.ps(0); tredg.ps({}), best.ps(0);
        
        pool(j, e[i]+1, s[i]){
            ll ind = sg.findkth(j+1, -(j!=s[i]), 0, n);
            tredg[nov].ps(kdo[ind]);
            
            if(j==s[i]) kdo[ind]=nov;
            else kdo[ind]=-1;
        }
        reverse(all(tredg[nov]));
        
        loop(j, 0, tredg[nov].size()){
            ll v=tredg[nov][j];
            po[nov]=max(po[nov], po[v]);
            if(j+1==tredg[nov].size()) vseb[nov]=max(vseb[nov], vseb[v]);
            else vseb[nov]=max(vseb[nov], po[v]);
        }
        //cout << po[nov]<<endl;
        
        fore(v, tredg[nov]) if(dp[nov] < dp[v] + (vseb[nov]<=r)){
            dp[nov] = dp[v] + (vseb[nov]<=r);
            best[nov]=best[v];
        }
    }
    
    return best.back();
}

Compilation message

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:3:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define loop(i, a, b) for(ll i=a;i<b;++i)
......
   86 |         loop(j, 0, tredg[nov].size()){
      |              ~~~~~~~~~~~~~~~~~~~~~~~
tournament.cpp:86:9: note: in expansion of macro 'loop'
   86 |         loop(j, 0, tredg[nov].size()){
      |         ^~~~
tournament.cpp:89:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             if(j+1==tredg[nov].size()) vseb[nov]=max(vseb[nov], vseb[v]);
      |                ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1108 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 3 ms 1236 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 4 ms 1264 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8392 KB Output is correct
2 Correct 61 ms 19072 KB Output is correct
3 Correct 28 ms 12436 KB Output is correct
4 Correct 82 ms 19064 KB Output is correct
5 Correct 62 ms 18472 KB Output is correct
6 Correct 65 ms 16360 KB Output is correct
7 Correct 66 ms 19172 KB Output is correct
8 Correct 62 ms 19068 KB Output is correct
9 Correct 25 ms 12412 KB Output is correct
10 Correct 32 ms 13088 KB Output is correct