oj.uz

Submission #307899

# Submission time Handle Problem Language Result Execution time Memory
307899 2020-09-29T13:51:59 Z Pajaraja Teams (IOI15_teams) C++17
100 / 100
 932 ms 174608 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 17 ms 23936 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 17 ms 23936 KB Output is correct
6 Correct 17 ms 23936 KB Output is correct
7 Correct 18 ms 23936 KB Output is correct
8 Correct 18 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 19 ms 23936 KB Output is correct
12 Correct 17 ms 23936 KB Output is correct
13 Correct 17 ms 23852 KB Output is correct
14 Correct 17 ms 23936 KB Output is correct
15 Correct 17 ms 23936 KB Output is correct
16 Correct 17 ms 23936 KB Output is correct
17 Correct 17 ms 23808 KB Output is correct
18 Correct 17 ms 23936 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 23936 KB Output is correct
22 Correct 18 ms 23808 KB Output is correct
23 Correct 17 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 23936 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 50296 KB Output is correct
2 Correct 80 ms 50392 KB Output is correct
3 Correct 79 ms 50296 KB Output is correct
4 Correct 86 ms 50936 KB Output is correct
5 Correct 40 ms 48760 KB Output is correct
6 Correct 40 ms 48760 KB Output is correct
7 Correct 41 ms 48760 KB Output is correct
8 Correct 40 ms 48824 KB Output is correct
9 Correct 42 ms 49136 KB Output is correct
10 Correct 40 ms 48752 KB Output is correct
11 Correct 40 ms 48880 KB Output is correct
12 Correct 41 ms 48880 KB Output is correct
13 Correct 51 ms 49008 KB Output is correct
14 Correct 57 ms 49648 KB Output is correct
15 Correct 73 ms 50296 KB Output is correct
16 Correct 75 ms 50168 KB Output is correct
17 Correct 43 ms 49400 KB Output is correct
18 Correct 43 ms 49272 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 51160 KB Output is correct
2 Correct 88 ms 51064 KB Output is correct
3 Correct 202 ms 54520 KB Output is correct
4 Correct 79 ms 50936 KB Output is correct
5 Correct 194 ms 49656 KB Output is correct
6 Correct 180 ms 49656 KB Output is correct
7 Correct 48 ms 49528 KB Output is correct
8 Correct 138 ms 49568 KB Output is correct
9 Correct 42 ms 49136 KB Output is correct
10 Correct 45 ms 49264 KB Output is correct
11 Correct 47 ms 49392 KB Output is correct
12 Correct 84 ms 49648 KB Output is correct
13 Correct 170 ms 49960 KB Output is correct
14 Correct 228 ms 52816 KB Output is correct
15 Correct 146 ms 51064 KB Output is correct
16 Correct 136 ms 51064 KB Output is correct
17 Correct 116 ms 50168 KB Output is correct
18 Correct 95 ms 50036 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 168776 KB Output is correct
2 Correct 538 ms 168824 KB Output is correct
3 Correct 879 ms 174608 KB Output is correct
4 Correct 537 ms 168824 KB Output is correct
5 Correct 519 ms 162680 KB Output is correct
6 Correct 475 ms 162476 KB Output is correct
7 Correct 161 ms 162680 KB Output is correct
8 Correct 413 ms 162552 KB Output is correct
9 Correct 144 ms 161768 KB Output is correct
10 Correct 146 ms 160744 KB Output is correct
11 Correct 175 ms 161416 KB Output is correct
12 Correct 281 ms 162024 KB Output is correct
13 Correct 740 ms 162632 KB Output is correct
14 Correct 932 ms 170556 KB Output is correct
15 Correct 545 ms 167412 KB Output is correct
16 Correct 561 ms 167496 KB Output is correct
17 Correct 316 ms 162400 KB Output is correct
18 Correct 301 ms 162468 KB Output is correct