oj.uz

Submission #705193

# Submission time Handle Problem Language Result Execution time Memory
705193 2023-03-03T14:37:08 Z bin9638 Teams (IOI15_teams) C++17
34 / 100
 4000 ms 49332 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fs first
#define sc second
#define N 500010
#define pb push_back
#define ii pair<int,int>

int n,cnt[N],l[N],r[N];
multiset<int>s;
vector<int>lis[N];

void init(int sl,int a[],int b[])
{
    n=sl;
    for(int i=1;i<=n;i++)
    {
        l[i]=a[i-1];
        r[i]=b[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        lis[l[i]].pb(r[i]);
    }
}

int can(int m,int sz[])
{
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<m;i++)
        cnt[sz[i]]++;
    s.clear();
    for(int i=1;i<=n;i++)
    {
        for(auto u:lis[i])
            s.insert(u);
        while(!s.empty()&&*s.begin()<i)
            s.erase(s.begin());
        if(1ll*cnt[i]*i>s.size())
            return 0;
        for(ll j=1ll*cnt[i]*i;j>=1;j--)
            s.erase(s.begin());
    }
    return 1;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
  //  ios::sync_with_stdio(0);
   // cin.tie(NULL);
   // cout.tie(NULL);
    int n;
    cin>>n;
    int a[n],b[n];
    for(int i=0;i<n;i++)
        cin>>a[i]>>b[i];
    init(n,a,b);
    int q;
    cin>>q;
    while(q--)
    {
        int m;
        cin>>m;
        int k[m];
        for(int j=0;j<m;j++)
            cin>>k[j];
        cout<<can(m,k)<<endl;
    }
    return 0;
}
#endif // SKY

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:42:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if(1ll*cnt[i]*i>s.size())
      |            ~~~~~~~~~~~~^~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 13908 KB Output is correct
2 Correct 7 ms 13968 KB Output is correct
3 Correct 12 ms 13952 KB Output is correct
4 Correct 11 ms 13908 KB Output is correct
5 Correct 14 ms 13968 KB Output is correct
6 Correct 7 ms 13984 KB Output is correct
7 Correct 13 ms 13908 KB Output is correct
8 Correct 12 ms 13908 KB Output is correct
9 Correct 13 ms 13976 KB Output is correct
10 Correct 12 ms 14036 KB Output is correct
11 Correct 9 ms 13900 KB Output is correct
12 Correct 13 ms 14048 KB Output is correct
13 Correct 15 ms 14044 KB Output is correct
14 Correct 12 ms 13908 KB Output is correct
15 Correct 13 ms 13908 KB Output is correct
16 Correct 12 ms 14024 KB Output is correct
17 Correct 14 ms 13996 KB Output is correct
18 Correct 14 ms 14032 KB Output is correct
19 Correct 12 ms 13908 KB Output is correct
20 Correct 13 ms 14000 KB Output is correct
21 Correct 11 ms 13972 KB Output is correct
22 Correct 13 ms 13908 KB Output is correct
23 Correct 16 ms 13908 KB Output is correct
24 Correct 13 ms 13908 KB Output is correct
25 Correct 11 ms 13968 KB Output is correct
26 Correct 14 ms 14036 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 18508 KB Output is correct
2 Correct 22 ms 18456 KB Output is correct
3 Correct 48 ms 20800 KB Output is correct
4 Correct 23 ms 19096 KB Output is correct
5 Correct 21 ms 17064 KB Output is correct
6 Correct 21 ms 16980 KB Output is correct
7 Correct 12 ms 17048 KB Output is correct
8 Correct 12 ms 17028 KB Output is correct
9 Correct 33 ms 21584 KB Output is correct
10 Correct 32 ms 21188 KB Output is correct
11 Correct 32 ms 21132 KB Output is correct
12 Correct 28 ms 20932 KB Output is correct
13 Correct 31 ms 19828 KB Output is correct
14 Correct 39 ms 22048 KB Output is correct
15 Correct 49 ms 20240 KB Output is correct
16 Correct 21 ms 18336 KB Output is correct
17 Correct 27 ms 18252 KB Output is correct
18 Correct 29 ms 18404 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 19176 KB Output is correct
2 Correct 36 ms 19208 KB Output is correct
3 Execution timed out 4040 ms 21136 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 39088 KB Output is correct
2 Correct 139 ms 38968 KB Output is correct
3 Execution timed out 4078 ms 49332 KB Time limit exceeded
4 Halted 0 ms 0 KB -