Submission #1018229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018229		huutuan	Teams (IOI15_teams)	C++14	100 / 100	2413 ms	115416 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>

using namespace std;

const int N=5e5+10, inf=1e9;

struct BIT2d{
   vector<pair<int, int>> t[N];
   int n;
   void init(int _n){
      n=_n;
      for (int i=1; i<=n; ++i) t[i].emplace_back(-1, 0);
   }
   void fake_update(int u, int v){
      for (int i=u; i<=n; i+=i&(-i)){
         t[i].emplace_back(v, 0);
      }
   }
   void compress(){
      for (int i=1; i<=n; ++i){
         sort(t[i].begin(), t[i].end());
         t[i].resize(unique(t[i].begin(), t[i].end())-t[i].begin());
      }
   }
   void update(int u, int v, int val){
      for (int i=u; i<=n; i+=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(v, -inf))-t[i].begin(); j<(int)t[i].size(); j+=j&(-j)){
            t[i][j].second+=val;
         }
      }
   }
   int get(int u, int v){
      int ans=0;
      for (int i=u; i; i-=i&(-i)){
         for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(v, inf))-t[i].begin()-1; j; j-=j&(-j)){
            ans+=t[i][j].second;
         }
      }
      return ans;
   }
   int get(int x, int y, int z, int t){
      if (x>z || y>t) return 0;
      return get(z, t)-get(x-1, t)-get(z, y-1)+get(x-1, y-1);
   }
} bit;

int 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]};
   bit.init(n);
   for (int i=1; i<=n; ++i) bit.fake_update(a[i].first, a[i].second);
   bit.compress();
   for (int i=1; i<=n; ++i) bit.update(a[i].first, a[i].second, 1);
}

int can(int M, int K[]) {
   map<int, int> mp;
   long long sum=0;
   for (int i=0; i<M; ++i) ++mp[K[i]], sum+=K[i];
   if (sum>n) return 0;
   vector<pair<int, int>> v(mp.begin(), mp.end());
   vector<int> del((int)v.size());
   for (int i=0; i<(int)v.size(); ++i){
      int cur=v[i].second*v[i].first;
      for (int j=i; j<(int)v.size(); ++j){
         int lx=1, rx=v[i].first;
         int ly=v[j].first, ry=j+1==(int)v.size()?n:v[j+1].first-1;
         int cnt=bit.get(lx, ly, rx, ry)-del[j];
         int d=min(cnt, cur);
         del[j]+=d;
         cur-=d;
         if (!cur) break;
      }
      if (cur) return 0;
   }
   return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'void BIT2d::update(int, int, int)':
teams.cpp:29:78: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   29 |          for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(v, -inf))-t[i].begin(); j<(int)t[i].size(); j+=j&(-j)){
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In member function 'int BIT2d::get(int, int)':
teams.cpp:37:90: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   37 |          for (int j=lower_bound(t[i].begin(), t[i].end(), make_pair(v, inf))-t[i].begin()-1; j; j-=j&(-j)){
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp: In member function 'int BIT2d::get(int, int, int, int)':
teams.cpp:43:37: warning: declaration of 't' shadows a member of 'BIT2d' [-Wshadow]
   43 |    int get(int x, int y, int z, int t){
      |                                 ~~~~^
teams.cpp:10:27: note: shadowed declaration is here
   10 |    vector<pair<int, int>> t[N];
      |                           ^

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