oj.uz

Submission #990231

# Submission time Handle Problem Language Result Execution time Memory
990231 2024-05-29T22:50:55 Z AdamGS Teams (IOI15_teams) C++17
100 / 100
 3756 ms 366240 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;
    while(po<ko) {
      int sr=(po+ko)/2;
      if(kwad(a, sr, P.back().st+1, Q[i].st)<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 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 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 1 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 2392 KB Output is correct
11 Correct 1 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 2532 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 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 1 ms 2396 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 1 ms 2396 KB Output is correct
24 Correct 1 ms 2444 KB Output is correct
25 Correct 1 ms 2428 KB Output is correct
26 Correct 0 ms 2396 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 72020 KB Output is correct
2 Correct 87 ms 71956 KB Output is correct
3 Correct 83 ms 71920 KB Output is correct
4 Correct 86 ms 72276 KB Output is correct
5 Correct 75 ms 72020 KB Output is correct
6 Correct 65 ms 72028 KB Output is correct
7 Correct 62 ms 72020 KB Output is correct
8 Correct 60 ms 72016 KB Output is correct
9 Correct 58 ms 72020 KB Output is correct
10 Correct 58 ms 72016 KB Output is correct
11 Correct 58 ms 72016 KB Output is correct
12 Correct 60 ms 72116 KB Output is correct
13 Correct 68 ms 71944 KB Output is correct
14 Correct 71 ms 72068 KB Output is correct
15 Correct 82 ms 72016 KB Output is correct
16 Correct 80 ms 71896 KB Output is correct
17 Correct 65 ms 71912 KB Output is correct
18 Correct 65 ms 72016 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 72424 KB Output is correct
2 Correct 88 ms 72296 KB Output is correct
3 Correct 613 ms 75348 KB Output is correct
4 Correct 83 ms 72320 KB Output is correct
5 Correct 405 ms 72360 KB Output is correct
6 Correct 387 ms 72532 KB Output is correct
7 Correct 67 ms 72528 KB Output is correct
8 Correct 281 ms 72280 KB Output is correct
9 Correct 54 ms 72020 KB Output is correct
10 Correct 59 ms 72280 KB Output is correct
11 Correct 93 ms 72272 KB Output is correct
12 Correct 527 ms 72320 KB Output is correct
13 Correct 620 ms 72532 KB Output is correct
14 Correct 862 ms 73812 KB Output is correct
15 Correct 292 ms 72532 KB Output is correct
16 Correct 289 ms 72532 KB Output is correct
17 Correct 251 ms 73812 KB Output is correct
18 Correct 232 ms 73808 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 358736 KB Output is correct
2 Correct 544 ms 358996 KB Output is correct
3 Correct 2631 ms 364572 KB Output is correct
4 Correct 518 ms 358736 KB Output is correct
5 Correct 1319 ms 358860 KB Output is correct
6 Correct 1206 ms 358752 KB Output is correct
7 Correct 349 ms 358996 KB Output is correct
8 Correct 986 ms 358736 KB Output is correct
9 Correct 321 ms 358740 KB Output is correct
10 Correct 327 ms 358704 KB Output is correct
11 Correct 794 ms 358736 KB Output is correct
12 Correct 2348 ms 358736 KB Output is correct
13 Correct 2762 ms 358900 KB Output is correct
14 Correct 3756 ms 361864 KB Output is correct
15 Correct 1022 ms 358996 KB Output is correct
16 Correct 1049 ms 366240 KB Output is correct
17 Correct 805 ms 365648 KB Output is correct
18 Correct 769 ms 365392 KB Output is correct