oj.uz

Submission #1057263

# Submission time Handle Problem Language Result Execution time Memory
1057263 2024-08-13T16:05:15 Z Faisal_Saqib Teams (IOI15_teams) C++17
0 / 100
 352 ms 167504 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-1 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
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 18780 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Incorrect 2 ms 18780 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 43868 KB Output is correct
2 Correct 33 ms 44040 KB Output is correct
3 Correct 31 ms 41812 KB Output is correct
4 Correct 32 ms 44208 KB Output is correct
5 Correct 18 ms 42840 KB Output is correct
6 Correct 18 ms 42716 KB Output is correct
7 Incorrect 19 ms 42844 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 44372 KB Output is correct
2 Correct 51 ms 44372 KB Output is correct
3 Correct 59 ms 47368 KB Output is correct
4 Correct 32 ms 44368 KB Output is correct
5 Correct 39 ms 43092 KB Output is correct
6 Correct 38 ms 43096 KB Output is correct
7 Incorrect 37 ms 43344 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 161628 KB Output is correct
2 Correct 295 ms 161624 KB Output is correct
3 Correct 352 ms 167504 KB Output is correct
4 Correct 242 ms 161620 KB Output is correct
5 Correct 131 ms 155728 KB Output is correct
6 Correct 140 ms 155724 KB Output is correct
7 Incorrect 130 ms 155732 KB Output isn't correct
8 Halted 0 ms 0 KB -