Submission #1017257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017257		huutuan	Teams (IOI15_teams)	C++14	34 / 100	4062 ms	32080 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);
   // sort(a+1, a+n+1, [&](pair<int, int> x, pair<int, int> y){
   //    if (x.second!=y.second) return x.second<y.second;
   //    return x.first<y.first;
   // });
   // 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);
   multiset<int> st;
   for (int i=0, j=1; i<M; ++i){
      while (j<=n && a[j].first<=K[i]){
         st.insert(a[j].second);
         ++j;
      }
      int cnt=K[i];
      while (st.size()){
         int tmp=*st.begin();
         st.erase(st.begin());
         if (tmp>=K[i]){
            --cnt;
            if (cnt==0) break;
         }
      }
      if (cnt) return 0;
   }
   // for (int i=1, j=0, cnt=K[0]; i<=n; ++i){
   //    if (a[i].first<=K[j] && K[j]<=a[i].second){
   //       --cnt;
   //       if (!cnt){
   //          ++j;
   //          if (j==M) return 1;
   //          cnt=K[j];
   //       }
   //    }
   // }
   // 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();
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:74:18: warning: declaration of 'st' shadows a global declaration [-Wshadow]
   74 |    multiset<int> st;
      |                  ^~
teams.cpp:51:3: note: shadowed declaration is here
   51 | } st;
      |   ^~

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