oj.uz

Submission #1057265

# Submission time Handle Problem Language Result Execution time Memory
1057265 2024-08-13T16:06:09 Z Faisal_Saqib Teams (IOI15_teams) C++17
77 / 100
 381 ms 167760 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-2 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 3 ms 18776 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 19032 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 2 ms 18792 KB Output is correct
10 Correct 2 ms 18776 KB Output is correct
11 Correct 2 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 18776 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 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 18776 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 33 ms 43860 KB Output is correct
2 Correct 31 ms 43868 KB Output is correct
3 Correct 30 ms 41996 KB Output is correct
4 Correct 33 ms 44368 KB Output is correct
5 Correct 18 ms 42840 KB Output is correct
6 Correct 18 ms 42840 KB Output is correct
7 Correct 18 ms 42972 KB Output is correct
8 Correct 19 ms 42844 KB Output is correct
9 Correct 20 ms 42708 KB Output is correct
10 Correct 17 ms 42780 KB Output is correct
11 Correct 17 ms 42704 KB Output is correct
12 Correct 17 ms 42736 KB Output is correct
13 Correct 21 ms 42988 KB Output is correct
14 Correct 24 ms 41252 KB Output is correct
15 Correct 31 ms 43868 KB Output is correct
16 Correct 29 ms 43892 KB Output is correct
17 Correct 21 ms 42864 KB Output is correct
18 Correct 20 ms 42872 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 44372 KB Output is correct
2 Correct 57 ms 44300 KB Output is correct
3 Correct 58 ms 47188 KB Output is correct
4 Correct 34 ms 44368 KB Output is correct
5 Correct 44 ms 43348 KB Output is correct
6 Correct 46 ms 43092 KB Output is correct
7 Correct 45 ms 43600 KB Output is correct
8 Correct 45 ms 43088 KB Output is correct
9 Correct 17 ms 42780 KB Output is correct
10 Correct 19 ms 43024 KB Output is correct
11 Correct 22 ms 42988 KB Output is correct
12 Correct 44 ms 42904 KB Output is correct
13 Correct 52 ms 43256 KB Output is correct
14 Correct 77 ms 45652 KB Output is correct
15 Correct 51 ms 44268 KB Output is correct
16 Correct 51 ms 44372 KB Output is correct
17 Correct 39 ms 43088 KB Output is correct
18 Correct 36 ms 43220 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 161872 KB Output is correct
2 Correct 308 ms 161836 KB Output is correct
3 Correct 352 ms 167760 KB Output is correct
4 Correct 231 ms 161620 KB Output is correct
5 Correct 149 ms 155728 KB Output is correct
6 Correct 150 ms 155732 KB Output is correct
7 Correct 165 ms 155728 KB Output is correct
8 Correct 159 ms 155728 KB Output is correct
9 Correct 89 ms 148416 KB Output is correct
10 Correct 91 ms 154772 KB Output is correct
11 Correct 106 ms 154644 KB Output is correct
12 Correct 155 ms 154820 KB Output is correct
13 Correct 197 ms 156496 KB Output is correct
14 Correct 381 ms 161488 KB Output is correct
15 Correct 240 ms 160356 KB Output is correct
16 Incorrect 251 ms 160252 KB Output isn't correct
17 Halted 0 ms 0 KB -