Submission #1015436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015436		cadmiumsky	Teams (IOI15_teams)	C++17	100 / 100	1434 ms	112400 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

#define lsb(x) (x & -x)
struct AIB {
   int faking = 1;
   vector<int> nrm;
   vector<int> tree;
   AIB(): faking(1) { nrm.clear(); tree.clear(); }
   void upd(int p, int x) {
      if(faking) { nrm.emplace_back(p); return; } 
      p = distance(begin(nrm), upper_bound(all(nrm), p));
      while(p > 0) tree[p] += x, p -= lsb(p);
      return;
   }
   int query(int p) {
      int sum  = 0;
      assert(!faking);
      p = distance(begin(nrm), lower_bound(all(nrm), p)) + 1;
      while(p < sz(tree)) sum += tree[p], p += lsb(p);
      return sum;
   }
   void donefaking() {
      faking = 0;
      sort(all(nrm));
      nrm.erase(unique(all(nrm)), end(nrm));
      tree.resize(sz(nrm) + 2, 0);
   }
};

struct AIB2D {
   vector<AIB> tree;
   void init(int n) {
      tree.assign(n + 2, AIB());
   }
   int query(int l, int r) {
      int sum = 0;
      
      
      while(l > 0) {
         sum += tree[l].query(r);
         l -= lsb(l);
      }
      
      return sum;
   }
   void upd(int l, int r, int x) {
      while(l < sz(tree)) 
         tree[l].upd(r, x),
         l += lsb(l);
      return;
   }
   void donefaking() { for(auto &x : tree) x.donefaking(); }
};

AIB2D sums;

vector<pii> pula;

int Query(int x) {
   int a = sums.query(x, x);
   return a;
}
int Query(int x, int not_y) {
   return sums.query(x, x) - sums.query(x, not_y);
}
void init(int n, int A[], int B[]) {
   sums.init(n + 1);
   for(int i = 0; i < n; i++) 
      pula.emplace_back(A[i], B[i]),
      sums.upd(A[i], B[i], 1);
   sums.donefaking();
   for(int i = 0; i < n; i++) 
      sums.upd(A[i], B[i], 1);
   return;
   
}

int can(int M, int K[]) {
   int sofar = 0;
   sort(K, K + M);
   
   vector<int> dp(M, 0);
   
   for(int i = 0; i < M; i++) {
      for(int j = i - 1, a = 0; a <= 78 && j >= 0; a++, j--) // trebuie sa incerc
         dp[i] = min(dp[i], dp[j] + Query(K[j], K[i]) - K[j]);
      if(dp[i] + Query(K[i]) - K[i] < 0) return 0;
   }
   return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'void AIB::upd(int, int)':
teams.cpp:23:19: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   23 |       p = distance(begin(nrm), upper_bound(all(nrm), p));
      |           ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'int AIB::query(int)':
teams.cpp:30:58: warning: conversion from 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   30 |       p = distance(begin(nrm), lower_bound(all(nrm), p)) + 1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:91:8: warning: unused variable 'sofar' [-Wunused-variable]
   91 |    int sofar = 0;
      |        ^~~~~

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