oj.uz

Submission #990232

# Submission time Handle Problem Language Result Execution time Memory
990232 2024-05-29T22:53:47 Z AdamGS Teams (IOI15_teams) C++17
100 / 100
 3632 ms 364636 KB 
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef struct item * pitem;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item {
  pitem l=nullptr, r=nullptr;
  int x=0;
};
const int LIM=5e5+7;
pitem roots[LIM];
pair<int,int>T[LIM];
int n, N=1;
void build(pitem v, int l, int r) {
  if(l==r) return;
  v->l=new item();
  v->r=new item();
  int mid=(l+r)/2;
  build(v->l, l, mid);
  build(v->r, mid+1, r);
}
pitem upd(pitem v, int l, int r, int a) {
  if(r<a || a<l) return v;
  pitem x=new item();
  x->x=v->x+1;
  if(l==r) {
    x->l=v->r;
    x->r=v->r;
    return x;
  }
  int mid=(l+r)/2;
  x->l=upd(v->l, l, mid, a);
  x->r=upd(v->r, mid+1, r, a);
  x->x=x->l->x+x->r->x;
  return x;
}
int cnt(pitem v, int l, int r, int a, int b) {
  if(r<a || b<l) return 0;
  if(a<=l && r<=b) return v->x;
  int mid=(l+r)/2;
  return cnt(v->l, l, mid, a, b)+cnt(v->r, mid+1, r, a, b);
}
int kwad(int l, int r, int a, int b) {
  return cnt(roots[r+1], 0, N-1, a, b)-cnt(roots[l], 0, N-1, a, b);
}
void init(int _N, int A[], int B[]) {
  n=_N;
  while(N<=n) N*=2;
  rep(i, n) T[i]={B[i], A[i]};
  sort(T, T+n);
  T[n]={n+1, 0};
  roots[0]=new item();
  build(roots[0], 0, N-1);
  rep(i, n+1) roots[i+1]=upd(roots[i], 0, N-1, T[i].nd);
}
int znajdz(int x) {
  int po=0, ko=n;
  while(po<ko) {
    int sr=(po+ko)/2;
    if(T[sr].st<x) po=sr+1; else ko=sr;
  }
  return po;
}
int can(int m, int K[]) {
  sort(K, K+m);
  int sum=0;
  rep(i, m) {
    sum+=K[i];
    if(sum>n) return 0;
  }
  vector<pair<int,int>>P;
  P.pb({0, n});
  vector<pair<int,int>>Q;
  Q.pb({K[0], K[0]});
  for(int i=1; i<m; ++i) if(K[i]!=Q.back().st) Q.pb({K[i], K[i]}); else Q[Q.size()-1].nd+=K[i];
  m=Q.size();
  rep(i, m) {
    int x=Q[i].nd, a=znajdz(Q[i].st);
    if(a==n) return 0;
    while(P.back().nd<a) P.pop_back();
    while(P.size()>0) {
      int c=kwad(a, P.back().nd, P.back().st+1, Q[i].st);
      if(c>=x) break;
      x-=c;
      a=P.back().nd+1;
      P.pop_back();
    }
    if(P.size()==0) return 0;
    int po=a, ko=n;
    int o=cnt(roots[a], 0, N-1, P.back().st+1, Q[i].st);
    while(po<ko) {
      int sr=(po+ko)/2;
      if(cnt(roots[sr+1], 0, N-1, P.back().st+1, Q[i].st)-o<x) po=sr+1; else ko=sr;
    }
    P.pb({Q[i].st, po});
  }
  return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:81:11: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   81 |   m=Q.size();
      |     ~~~~~~^~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 72008 KB Output is correct
2 Correct 84 ms 72016 KB Output is correct
3 Correct 80 ms 72016 KB Output is correct
4 Correct 98 ms 72408 KB Output is correct
5 Correct 65 ms 72060 KB Output is correct
6 Correct 64 ms 72016 KB Output is correct
7 Correct 66 ms 72020 KB Output is correct
8 Correct 63 ms 72020 KB Output is correct
9 Correct 60 ms 72024 KB Output is correct
10 Correct 60 ms 72132 KB Output is correct
11 Correct 59 ms 72080 KB Output is correct
12 Correct 60 ms 72020 KB Output is correct
13 Correct 66 ms 72020 KB Output is correct
14 Correct 68 ms 72036 KB Output is correct
15 Correct 84 ms 72020 KB Output is correct
16 Correct 78 ms 72020 KB Output is correct
17 Correct 64 ms 71952 KB Output is correct
18 Correct 63 ms 72008 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 72352 KB Output is correct
2 Correct 98 ms 72276 KB Output is correct
3 Correct 502 ms 75344 KB Output is correct
4 Correct 105 ms 72480 KB Output is correct
5 Correct 288 ms 72280 KB Output is correct
6 Correct 247 ms 72328 KB Output is correct
7 Correct 71 ms 72272 KB Output is correct
8 Correct 223 ms 72280 KB Output is correct
9 Correct 59 ms 72016 KB Output is correct
10 Correct 60 ms 72392 KB Output is correct
11 Correct 87 ms 72520 KB Output is correct
12 Correct 436 ms 72276 KB Output is correct
13 Correct 579 ms 72528 KB Output is correct
14 Correct 803 ms 73808 KB Output is correct
15 Correct 217 ms 72528 KB Output is correct
16 Correct 210 ms 72372 KB Output is correct
17 Correct 183 ms 72784 KB Output is correct
18 Correct 169 ms 72528 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 358712 KB Output is correct
2 Correct 540 ms 358740 KB Output is correct
3 Correct 2544 ms 364636 KB Output is correct
4 Correct 602 ms 358696 KB Output is correct
5 Correct 1014 ms 359000 KB Output is correct
6 Correct 944 ms 358736 KB Output is correct
7 Correct 353 ms 358736 KB Output is correct
8 Correct 876 ms 358996 KB Output is correct
9 Correct 299 ms 358740 KB Output is correct
10 Correct 306 ms 358768 KB Output is correct
11 Correct 714 ms 358744 KB Output is correct
12 Correct 2029 ms 358808 KB Output is correct
13 Correct 2514 ms 358992 KB Output is correct
14 Correct 3632 ms 361884 KB Output is correct
15 Correct 810 ms 358996 KB Output is correct
16 Correct 859 ms 358996 KB Output is correct
17 Correct 618 ms 358740 KB Output is correct
18 Correct 653 ms 358736 KB Output is correct