Submission #1057034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057034		mychecksedad	Radio Towers (IOI22_towers)	C++17	23 / 100	4083 ms	6960 KiB

towers

#include "towers.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define en cout << '\n'
#define pi pair<int,int>
#define vi vector<int> 
#define ff first
#define ss second

struct Fenwick{
  vector<int> t;
  int n;
  Fenwick(int n): n(n){
    t.resize(n+1);
  }
  void add(int v){
    while(v <= n){
      t[v]++;
      v += v&-v;
    }
  }
  int get(int v){
    int res = 0;
    while(v > 0){
      res += t[v];
      v -= v&-v;
    }
    return res;
  }
};


void op(vector<int> &a, vector<int> &A, vector<int> &B){
  if(a.size() <= 1){
    A = a;
    B.pb(0);
    return;
  }
  A.pb(a[0]);
  A.pb(a[1]);
  B.pb(0);
  B.pb(1);
  for(int i = 2; i < a.size(); ++i){
    if(a[i] > A.back() && A.back() > A[int(A.size()) - 2]){
      A.pop_back();
      B.pop_back();
      A.pb(a[i]);
      B.pb(i);
    }else if(a[i] < A.back() && A.back() < A[int(A.size()) - 2]){
      A.pop_back();
      B.pop_back();
      A.pb(a[i]);
      B.pb(i);
    }else{
      A.pb(a[i]);
      B.pb(i);
    }
  }
  
}
int n;
vector<int> A, B, A2, A1, B1, B2, a;
Fenwick f(1000000);
void init(int nn, std::vector<int> aa) { n=nn;a=aa;
  if(n == 1) return;
  op(a, A, B);
  // elimizde a b var cool
  // if(A[0] > A[1]){
  //   for(int i = 0; i < A.size(); i += 2){
  //     f.add(B[i]);
  //   }
  // }else{
  //   for(int i = 1; i < A.size(); i += 2){
  //     f.add(B[i]);
  //   }
  // }
  for(int i = 1; i + 1 < n; ++i){
    if(a[i] > a[i - 1] && a[i] > a[i + 1]) f.add(i + 1);
  }
}

int max_towers(int L, int R, int D) { ++L, ++R;
  if(n == 1 || L == R) return 1;
  --L, --R;
  vector<int> X;
  for(int i = L; i <= R; ++i) X.pb(a[i]);
  A.clear();
  B.clear();
  op(X, A, B);

  // set<pair<int, int>> s;
  // priority_queue<pair<int, int>> q;
  // for(int i = 0; i < A.size(); ++i){
    // s.insert({i, A[i]});
    // if(i > 0 && i + 1 < A.size()){
    //   if(A < )
    //   q.push({-min(A[i + 1] - A[i], A[i - 1] - A[i]), i});
    // }
  // }
  bool ok = 1;
  while(ok){
    ok = 0;
    if(A.size() == 1) return 1;
    int mindif = 1000000000, pos = -1;
    for(int i = 0; i < A.size(); ++i){
      if(i + 2 < A.size() && A[i] < A[i + 1]){  
        if(mindif > A[i + 1] - A[i]){
          mindif = A[i + 1] - A[i];
          pos = i;
        }
      }
      if(i > 1 && A[i] < A[i - 1]){  
        if(mindif > A[i - 1] - A[i]){
          mindif = A[i - 1] - A[i];
          pos = i;
        }
      }
    }
    if(pos == -1) break;
    if(mindif < D)
      A.erase(A.begin() + pos), ok = 1;
    else 
      break;
    for(int i = 0; i + 2 < A.size(); ++i){
      if(A[i] < A[i + 1] && A[i + 1] < A[i + 2]){
        A.erase(A.begin() + i + 1); 
        --i;
        continue;
      }
      if(A[i] > A[i + 1] && A[i + 1] > A[i + 2]){
        A.erase(A.begin() + i + 1);
        --i;
        continue;
      }
    }
  }
  // for(auto k: A) cout << k<< ' '; 
  int ans = 0;
  for(int i = 1; i + 1 < A.size(); ++i){
    if(A[i] > A[i - 1] && A[i] > A[i + 1] ) ++ans;
  }
  return max(ans+1,1);
}

Compilation message (stderr)

towers.cpp: In function 'void op(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
towers.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int i = 2; i < a.size(); ++i){
      |                  ~~^~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for(int i = 0; i < A.size(); ++i){
      |                    ~~^~~~~~~~~~
towers.cpp:109:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |       if(i + 2 < A.size() && A[i] < A[i + 1]){
      |          ~~~~~~^~~~~~~~~~
towers.cpp:127:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i = 0; i + 2 < A.size(); ++i){
      |                    ~~~~~~^~~~~~~~~~
towers.cpp:142:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for(int i = 1; i + 1 < A.size(); ++i){
      |                  ~~~~~~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23