oj.uz

Submission #306480

# Submission time Handle Problem Language Result Execution time Memory
306480 2020-09-25T17:02:32 Z Pajaraja Teams (IOI15_teams) C++17
100 / 100
 943 ms 170444 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define MAXN 500007
using namespace std;
int per[25*MAXN],lc[25*MAXN],rc[25*MAXN],t,n,st[MAXN],dp[MAXN],m,nxt[MAXN],prv[MAXN],top,fas[MAXN];
vector<int> l[MAXN],v,c,z[MAXN];
void makeper(int l,int r,int ind)
{
    if(l==r) return;
    int s=(l+r)/2;
    lc[ind]=++t;
    makeper(l,s,lc[ind]);
    rc[ind]=++t;
    makeper(s+1,r,rc[ind]);
}
void makenewper(int l,int r,int v,int ind,int inh)
{
    per[ind]=per[inh]+1;
    if(l==r) return;
    int s=(l+r)/2;
    if(s>=v)
    {
        rc[ind]=rc[inh];
        lc[ind]=++t;
        makenewper(l,s,v,lc[ind],lc[inh]);
    }
    else
    {
        lc[ind]=lc[inh];
        rc[ind]=++t;
        makenewper(s+1,r,v,rc[ind],rc[inh]);
    }
}
int query(int l,int r,int lt,int rt,int ind)
{
    if(l>=lt && r<=rt) return per[ind];
    if(r<lt || l>rt) return 0;
    int s=(l+r)/2;
    return query(l,s,lt,rt,lc[ind])+query(s+1,r,lt,rt,rc[ind]);
}
void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0;i<n;i++) l[B[i]].push_back(A[i]);
    makeper(1,n,t);
    int last=0;
    for(int i=n;i>=0;i--)
    {
        for(int j=0;j<l[i].size();j++) {int newlast=++t; makenewper(1,n,l[i][j],newlast,last); last=newlast;}
        st[i]=last;
    }
}
int overtake(int a,int b)
{
    int l=b+1,r=m-1;
    if(dp[a]+query(1,n,v[a]+1,v[b],st[v[m-1]])>dp[b]) return m;
    while(l!=r)
    {
        int s=(l+r)/2;
        if(dp[a]+query(1,n,v[a]+1,v[b],st[v[s]])<=dp[b]) r=s;
        else l=s+1;
    }
    return l;
}
int can(int M, int K[])
{
    sort(K,K+M);
    v.clear(); c.clear();
    int sz=0; for(int i=0;i<M;i++) {sz+=K[i]; if(sz>n) return 0;}
	int cnt=0;
	v.push_back(0); c.push_back(0);
	for(int i=0;i<M;i++)
    {
        cnt++;
        if(i==M-1 || K[i]!=K[i+1]) {v.push_back(K[i]); c.push_back(cnt); cnt=0;}
    }
    m=v.size(); prv[0]=nxt[0]=-1; dp[0]=0; top=0;
    for(int i=0;i<=m;i++) z[i].clear();
    for(int i=1;i<m;i++)
    {
        for(int j=0;j<z[i].size();j++) if(!fas[z[i][j]])
        {
            int t=z[i][j];
            if(t==top) {fas[top]=true; top=prv[t]; nxt[top]=-1; continue;}
            nxt[prv[t]]=nxt[t];
            prv[nxt[t]]=prv[t];
            z[max(i,overtake(prv[t],nxt[t]))].push_back(nxt[t]);
            fas[t]=true;
        }
        dp[i]=query(1,n,v[top]+1,v[i],st[v[i]])+dp[top];
        fas[i]=false; nxt[i]=-1; prv[i]=top; nxt[top]=i;
        dp[i]-=c[i]*v[i];
        if(dp[i]<0) return 0;
        while(dp[i]<dp[top]) {fas[top]=true; top=prv[top]; nxt[top]=i; prv[i]=top;}
        top=i;
        if(i!=m-1) z[overtake(prv[top],top)].push_back(top);
    }
    return 1;
}

Compilation message

teams.cpp: In function 'void makeper(int, int, int)':
teams.cpp:7:33: warning: declaration of 'l' shadows a global declaration [-Wshadow]
    7 | void makeper(int l,int r,int ind)
      |                                 ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'void makenewper(int, int, int, int, int)':
teams.cpp:16:50: warning: declaration of 'v' shadows a global declaration [-Wshadow]
   16 | void makenewper(int l,int r,int v,int ind,int inh)
      |                                                  ^
teams.cpp:6:21: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |                     ^
teams.cpp:16:50: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   16 | void makenewper(int l,int r,int v,int ind,int inh)
      |                                                  ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'int query(int, int, int, int, int)':
teams.cpp:34:44: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   34 | int query(int l,int r,int lt,int rt,int ind)
      |                                            ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for(int j=0;j<l[i].size();j++) {int newlast=++t; makenewper(1,n,l[i][j],newlast,last); last=newlast;}
      |                     ~^~~~~~~~~~~~
teams.cpp: In function 'int overtake(int, int)':
teams.cpp:55:9: warning: declaration of 'l' shadows a global declaration [-Wshadow]
   55 |     int l=b+1,r=m-1;
      |         ^
teams.cpp:6:13: note: shadowed declaration is here
    6 | vector<int> l[MAXN],v,c,z[MAXN];
      |             ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:77:13: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   77 |     m=v.size(); prv[0]=nxt[0]=-1; dp[0]=0; top=0;
      |       ~~~~~~^~
teams.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int j=0;j<z[i].size();j++) if(!fas[z[i][j]])
      |                     ~^~~~~~~~~~~~
teams.cpp:83:17: warning: declaration of 't' shadows a global declaration [-Wshadow]
   83 |             int t=z[i][j];
      |                 ^
teams.cpp:5:42: note: shadowed declaration is here
    5 | int per[25*MAXN],lc[25*MAXN],rc[25*MAXN],t,n,st[MAXN],dp[MAXN],m,nxt[MAXN],prv[MAXN],top,fas[MAXN];
      |                                          ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 18 ms 23936 KB Output is correct
4 Correct 17 ms 23936 KB Output is correct
5 Correct 17 ms 23968 KB Output is correct
6 Correct 17 ms 23936 KB Output is correct
7 Correct 17 ms 23936 KB Output is correct
8 Correct 17 ms 23936 KB Output is correct
9 Correct 17 ms 23936 KB Output is correct
10 Correct 17 ms 23936 KB Output is correct
11 Correct 17 ms 23808 KB Output is correct
12 Correct 17 ms 23936 KB Output is correct
13 Correct 18 ms 23936 KB Output is correct
14 Correct 18 ms 23936 KB Output is correct
15 Correct 17 ms 23808 KB Output is correct
16 Correct 17 ms 23936 KB Output is correct
17 Correct 18 ms 23808 KB Output is correct
18 Correct 17 ms 23808 KB Output is correct
19 Correct 17 ms 23808 KB Output is correct
20 Correct 17 ms 23808 KB Output is correct
21 Correct 17 ms 23808 KB Output is correct
22 Correct 17 ms 23808 KB Output is correct
23 Correct 18 ms 23808 KB Output is correct
24 Correct 17 ms 23808 KB Output is correct
25 Correct 17 ms 23808 KB Output is correct
26 Correct 18 ms 23808 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 49144 KB Output is correct
2 Correct 80 ms 49148 KB Output is correct
3 Correct 81 ms 49144 KB Output is correct
4 Correct 83 ms 49656 KB Output is correct
5 Correct 40 ms 47992 KB Output is correct
6 Correct 41 ms 48120 KB Output is correct
7 Correct 41 ms 47992 KB Output is correct
8 Correct 39 ms 47992 KB Output is correct
9 Correct 41 ms 48240 KB Output is correct
10 Correct 40 ms 48240 KB Output is correct
11 Correct 39 ms 48240 KB Output is correct
12 Correct 41 ms 48240 KB Output is correct
13 Correct 51 ms 48112 KB Output is correct
14 Correct 55 ms 48624 KB Output is correct
15 Correct 71 ms 49040 KB Output is correct
16 Correct 71 ms 49016 KB Output is correct
17 Correct 43 ms 48248 KB Output is correct
18 Correct 42 ms 48248 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 49528 KB Output is correct
2 Correct 98 ms 49588 KB Output is correct
3 Correct 194 ms 52472 KB Output is correct
4 Correct 83 ms 49656 KB Output is correct
5 Correct 182 ms 48504 KB Output is correct
6 Correct 167 ms 48508 KB Output is correct
7 Correct 48 ms 48376 KB Output is correct
8 Correct 137 ms 48468 KB Output is correct
9 Correct 43 ms 48376 KB Output is correct
10 Correct 42 ms 48496 KB Output is correct
11 Correct 47 ms 48496 KB Output is correct
12 Correct 85 ms 48624 KB Output is correct
13 Correct 165 ms 48568 KB Output is correct
14 Correct 217 ms 50936 KB Output is correct
15 Correct 129 ms 49548 KB Output is correct
16 Correct 131 ms 49528 KB Output is correct
17 Correct 112 ms 48632 KB Output is correct
18 Correct 93 ms 48688 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 164420 KB Output is correct
2 Correct 572 ms 164580 KB Output is correct
3 Correct 879 ms 170444 KB Output is correct
4 Correct 540 ms 164728 KB Output is correct
5 Correct 539 ms 158456 KB Output is correct
6 Correct 490 ms 158328 KB Output is correct
7 Correct 161 ms 158456 KB Output is correct
8 Correct 418 ms 158380 KB Output is correct
9 Correct 150 ms 157544 KB Output is correct
10 Correct 143 ms 157772 KB Output is correct
11 Correct 175 ms 157800 KB Output is correct
12 Correct 281 ms 157800 KB Output is correct
13 Correct 772 ms 158536 KB Output is correct
14 Correct 943 ms 166516 KB Output is correct
15 Correct 555 ms 163188 KB Output is correct
16 Correct 566 ms 163056 KB Output is correct
17 Correct 315 ms 158304 KB Output is correct
18 Correct 299 ms 158116 KB Output is correct