oj.uz

Submission #1057261

# Submission time Handle Problem Language Result Execution time Memory
1057261 2024-08-13T16:04:48 Z Faisal_Saqib Teams (IOI15_teams) C++17
100 / 100
 400 ms 167508 KB 
#pragma optimize("O2")
#include <bits/stdc++.h>
// #include "teams.h"
using namespace std;
const int N=5e5+1;
#define lc second.first
#define rc second.second
#define sum first
pair<int,pair<int,int>> seg[50000001];
int nfi=0;

int build(int l,int&r)
{
    int cur=nfi;
    seg[cur].sum=0;
    nfi++;
    if(l==r)
        return cur;
    int mid=(l+r)/2;
    seg[cur].lc=build(l,mid);
    seg[cur].rc=build(mid+1,r);
    return cur;
}

// node =def= seg[node] is being changed
// l,r are the range of seg[node](current segment)
// x is the index to be update
int update(int&node,int l,int&r,int&x)
{
    int cur=nfi;
    nfi++;
    seg[cur]=seg[node];
    if(l==r)
    {
        seg[cur].sum++;
        return cur;
    }
    int mid=(l+r)/2;
    if(x<=mid)
        seg[cur].lc=update(seg[cur].lc,l,mid,x);
    else
        seg[cur].rc=update(seg[cur].rc,mid+1,r,x);
    seg[cur].sum=seg[seg[cur].lc].sum+seg[seg[cur].rc].sum;
    return cur;
}

int get(int&node,int l,int&r,int&ql,int&qr)
{
    if(ql<=l and r<=qr)
        return seg[node].sum;
    int mid=(l+r)/2;
    if(qr<=mid)
        return get(seg[node].lc,l,mid,ql,qr);
    else if(mid<ql)
        return get(seg[node].rc,mid+1,r,ql,qr);
    else
        return get(seg[node].lc,l,mid,ql,qr)+get(seg[node].rc,mid+1,r,ql,qr);
}

int n,till[N],cup;
vector<int> add[N];
void init(int Ng, int A[], int B[])
{
    n=Ng;
    for(int i=0;i<n;i++)
    {
        add[A[i]].push_back(B[i]);
    }
    till[0]=build(1,n);
    cup=till[0];
    for(int i=1;i<=n;i++)
    {
        for(auto&j:add[i])
            cup=update(cup,1,n,j);
        till[i]=cup;
    }
}
int Contains(int&l,int&r)
{
    return get(till[l],1,n,r,n);
}
int cnt[N]; // cnt of x
int dp[N];// dp
int can(int m, int k[])
{
    int sm=0;
    for(int i=0;i<m;i++)
    {
        sm+=k[i];
        if(sm>n)
        {
            //Not Possible
            return 0;
        }
    }
    for(int i=0;i<m;i++)
        cnt[k[i]]++;
    sort(k,k+m);
    int mp=unique(k,k+m)-k;
    //Here we write the dp solution
    int mi=1e9;
    for(int i=0;i<mp;i++)
    {
        int x=k[i];
        int sz=cnt[x]*x;
        int cntx=Contains(x,x);
        dp[i]=cntx-sz;
        for(int j=i-1;j>=i-7 and j>=0;j--)
            dp[i]=min(dp[i],dp[j] + cntx - Contains(k[j],x) - sz);
        mi=min(mi,dp[i]);
    }
    for(int i=0;i<mp;i++)
        cnt[k[i]]=0;
    return (mi>=0);
}

Compilation message

teams.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("O2")
      | 
teams.cpp: In function 'int can(int, int*)':
teams.cpp:99:25: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   99 |     int mp=unique(k,k+m)-k;
      |            ~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43864 KB Output is correct
2 Correct 32 ms 43860 KB Output is correct
3 Correct 31 ms 41820 KB Output is correct
4 Correct 32 ms 44296 KB Output is correct
5 Correct 19 ms 42844 KB Output is correct
6 Correct 18 ms 42884 KB Output is correct
7 Correct 18 ms 42844 KB Output is correct
8 Correct 18 ms 42704 KB Output is correct
9 Correct 18 ms 42708 KB Output is correct
10 Correct 17 ms 42708 KB Output is correct
11 Correct 17 ms 42704 KB Output is correct
12 Correct 17 ms 42708 KB Output is correct
13 Correct 21 ms 42980 KB Output is correct
14 Correct 24 ms 41020 KB Output is correct
15 Correct 30 ms 43888 KB Output is correct
16 Correct 29 ms 43864 KB Output is correct
17 Correct 22 ms 42844 KB Output is correct
18 Correct 20 ms 42836 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 44376 KB Output is correct
2 Correct 93 ms 44372 KB Output is correct
3 Correct 57 ms 47188 KB Output is correct
4 Correct 32 ms 44368 KB Output is correct
5 Correct 81 ms 43204 KB Output is correct
6 Correct 80 ms 43092 KB Output is correct
7 Correct 81 ms 43348 KB Output is correct
8 Correct 79 ms 43092 KB Output is correct
9 Correct 18 ms 42708 KB Output is correct
10 Correct 19 ms 42964 KB Output is correct
11 Correct 24 ms 43044 KB Output is correct
12 Correct 73 ms 42892 KB Output is correct
13 Correct 81 ms 43212 KB Output is correct
14 Correct 65 ms 45592 KB Output is correct
15 Correct 69 ms 44404 KB Output is correct
16 Correct 67 ms 44372 KB Output is correct
17 Correct 58 ms 43088 KB Output is correct
18 Correct 51 ms 42960 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 161860 KB Output is correct
2 Correct 389 ms 161872 KB Output is correct
3 Correct 359 ms 167508 KB Output is correct
4 Correct 242 ms 161640 KB Output is correct
5 Correct 225 ms 155732 KB Output is correct
6 Correct 229 ms 155732 KB Output is correct
7 Correct 235 ms 155732 KB Output is correct
8 Correct 225 ms 155832 KB Output is correct
9 Correct 84 ms 148416 KB Output is correct
10 Correct 101 ms 154632 KB Output is correct
11 Correct 139 ms 154816 KB Output is correct
12 Correct 225 ms 155032 KB Output is correct
13 Correct 278 ms 156488 KB Output is correct
14 Correct 360 ms 161388 KB Output is correct
15 Correct 285 ms 160328 KB Output is correct
16 Correct 331 ms 160340 KB Output is correct
17 Correct 195 ms 155252 KB Output is correct
18 Correct 181 ms 155064 KB Output is correct