Submission #1017290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017290		huutuan	Teams (IOI15_teams)	C++14	0 / 100	4040 ms	130732 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>

using namespace std;

struct Node{
   vector<int> data;
   void merge(const Node &tl, const Node &tr){
      data.resize(tl.data.size()+tr.data.size());
      std::merge(tl.data.begin(), tl.data.end(), tr.data.begin(), tr.data.end(), data.begin());
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void build(int k, int l, int r, pair<int, int> a[]){
      if (l==r){
         t[k].data.push_back(a[l].second);
         return;
      }
      int mid=(l+r)>>1;
      build(k<<1, l, mid, a);
      build(k<<1|1, mid+1, r, a);
      t[k].merge(t[k<<1], t[k<<1|1]);
   }
   // int cnt;
   // int count(int k, int val){
   //    return upper_bound(t[k].data.begin(), t[k].data.end(), val)-t[k].data.begin();
   // }
   int get(int k, int l, int r, int L, int R, int val){
      if (r<L || R<l) return 0;
      if (L<=l && r<=R) return t[k].data.end()-lower_bound(t[k].data.begin(), t[k].data.end(), val);
      int mid=(l+r)>>1;
      return get(k<<1, l, mid, L, R, val)+get(k<<1|1, mid+1, r, L, R, val);
   }
   // int walk(int k, int l, int r, int L, int R, int val){
   //    if (r<L || R<l) return 0;
   //    if (L<=l && r<=R){
   //       int cc=count(k, val);
   //       if (cc<cnt){
   //          cnt-=cc;
   //          return 0;
   //       }
   //    }
   //    if (l==r) return t[k].data[0]<=val && cnt==1;
   //    int mid=(l+r)>>1;
   //    int ans=walk(k<<1, l, mid, L, R, val);
   //    if (ans) return ans;
   //    return walk(k<<1|1, mid+1, r, L, R, val);
   // }
} st;

const int N=5e5+10;
int n, pos[N];
pair<int, int> a[N];

void init(int _N, int _A[], int _B[]) {
   n=_N;
   for (int i=1; i<=n; ++i) a[i]={_A[i-1], _B[i-1]};
   sort(a+1, a+n+1);
   st.init(n);
   st.build(1, 1, n, a);
   for (int i=1; i<=n; ++i) pos[i]=0;
   for (int i=1; i<=n; ++i) pos[a[i].first]=max(pos[a[i].first], i);
   for (int i=2; i<=n; ++i) pos[i]=max(pos[i], pos[i-1]);
}

int can(int M, int K[]) {
   sort(K, K+M);
   for (int i=0; i<M; ++i){
      int sum=0;
      for (int j=i; j<M; ++j){
         sum+=K[j];
         if (st.get(1, 1, n, 1, pos[K[j]], K[i])<sum){
            return 0;
         }
      }
   }
   return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int SegmentTree::get(int, int, int, int, int, int)':
teams.cpp:38:47: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   38 |       if (L<=l && r<=R) return t[k].data.end()-lower_bound(t[k].data.begin(), t[k].data.end(), val);
      |                                ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23