oj.uz

Submission #1057264

# Submission time Handle Problem Language Result Execution time Memory
1057264 2024-08-13T16:05:47 Z Faisal_Saqib Teams (IOI15_teams) C++17
100 / 100
 414 ms 167572 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-3 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 3 ms 18780 KB Output is correct
4 Correct 2 ms 18872 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 3 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 2 ms 18780 KB Output is correct
12 Correct 2 ms 18776 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 18780 KB Output is correct
17 Correct 2 ms 18780 KB Output is correct
18 Correct 2 ms 18916 KB Output is correct
19 Correct 2 ms 18780 KB Output is correct
20 Correct 2 ms 18880 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 18776 KB Output is correct
25 Correct 2 ms 18780 KB Output is correct
26 Correct 2 ms 18780 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 43860 KB Output is correct
2 Correct 33 ms 43860 KB Output is correct
3 Correct 32 ms 41812 KB Output is correct
4 Correct 32 ms 44380 KB Output is correct
5 Correct 18 ms 42944 KB Output is correct
6 Correct 20 ms 42844 KB Output is correct
7 Correct 18 ms 42980 KB Output is correct
8 Correct 18 ms 42840 KB Output is correct
9 Correct 17 ms 42788 KB Output is correct
10 Correct 18 ms 42708 KB Output is correct
11 Correct 17 ms 42776 KB Output is correct
12 Correct 18 ms 42704 KB Output is correct
13 Correct 21 ms 42968 KB Output is correct
14 Correct 23 ms 41244 KB Output is correct
15 Correct 30 ms 43904 KB Output is correct
16 Correct 29 ms 43892 KB Output is correct
17 Correct 20 ms 42840 KB Output is correct
18 Correct 20 ms 42844 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 44368 KB Output is correct
2 Correct 64 ms 44372 KB Output is correct
3 Correct 61 ms 47184 KB Output is correct
4 Correct 37 ms 44372 KB Output is correct
5 Correct 54 ms 43504 KB Output is correct
6 Correct 52 ms 43088 KB Output is correct
7 Correct 52 ms 43344 KB Output is correct
8 Correct 51 ms 43100 KB Output is correct
9 Correct 17 ms 42704 KB Output is correct
10 Correct 19 ms 43036 KB Output is correct
11 Correct 22 ms 42964 KB Output is correct
12 Correct 50 ms 42996 KB Output is correct
13 Correct 60 ms 43268 KB Output is correct
14 Correct 60 ms 45648 KB Output is correct
15 Correct 54 ms 44372 KB Output is correct
16 Correct 63 ms 44368 KB Output is correct
17 Correct 42 ms 43088 KB Output is correct
18 Correct 39 ms 42964 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 161876 KB Output is correct
2 Correct 315 ms 161620 KB Output is correct
3 Correct 346 ms 167572 KB Output is correct
4 Correct 232 ms 161616 KB Output is correct
5 Correct 163 ms 155728 KB Output is correct
6 Correct 165 ms 155724 KB Output is correct
7 Correct 182 ms 155736 KB Output is correct
8 Correct 163 ms 155824 KB Output is correct
9 Correct 84 ms 148420 KB Output is correct
10 Correct 89 ms 154820 KB Output is correct
11 Correct 110 ms 154804 KB Output is correct
12 Correct 173 ms 154848 KB Output is correct
13 Correct 232 ms 156448 KB Output is correct
14 Correct 414 ms 161488 KB Output is correct
15 Correct 249 ms 160328 KB Output is correct
16 Correct 247 ms 160200 KB Output is correct
17 Correct 151 ms 155060 KB Output is correct
18 Correct 147 ms 155032 KB Output is correct