Submission #1017227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017227		huutuan	Teams (IOI15_teams)	C++14	0 / 100	366 ms	134740 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].first);
         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 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]=n+1;
   for (int i=1; i<=n; ++i) pos[a[i].second]=min(pos[a[i].second], i);
   for (int i=1; i<n; ++i) pos[i]=min(pos[i], pos[i+1]);
}

int can(int M, int K[]) {
   sort(K, K+M);
   int cur=1;
   for (int i=0; i<M; ++i){
      int k=K[i];
      if (pos[k]==n+1) return 0;
      cur=max(cur, pos[k]);
      st.cnt=k;
      int id=st.walk(1, 1, n, cur, n, k);
      if (!id) return 0;
      cur=id+1;
   }
   return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'int SegmentTree::count(int, int)':
teams.cpp:34:66: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   34 |       return upper_bound(t[k].data.begin(), t[k].data.end(), val)-t[k].data.begin();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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