Submission #307942

#	Time	Username	Problem	Language	Result	Execution time	Memory
307942		AlexLuchianov	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	468 ms	107384 KiB

constellation3

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <set>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

class SegmentTree{
private:
  std::vector<std::pair<int,int>> aint;
public:
  SegmentTree(int n) {
    aint.resize(1 + 4 * n);
  }
  void computenode(int node, int from, int to) {
    aint[node] = std::max(aint[node * 2] , aint[node * 2 + 1]);
  }
  
  void build(int node, int from, int to, std::vector<int> &aux) {
    if(from < to) {
      int mid = (from + to) / 2;
      build(node * 2, from, mid, aux);
      build(node * 2 + 1, mid + 1, to, aux);
      computenode(node, from, to);
    } else
      aint[node] = {aux[from], from};
  }

  std::pair<int,int> query(int node, int from, int to, int x, int y) {
    if(from == x && to == y)
      return aint[node];
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y);
      else
        return std::max(query(node * 2, from, mid, x, mid),
                        query(node * 2 + 1, mid + 1, to, mid + 1, y));
    }
  }
};

int const nmax = 200000;

ll const inf = 1000000000000000000;

std::vector<std::vector<std::pair<int,int>>> event;

class SpecialSet{
public:
  std::set<std::pair<int, ll>> myset;
  ll offset = 0;
  void update(ll val) {
    offset += val;
  }
  void _insert(std::pair<int, ll> val) {
    val.second -= offset;
    std::set<std::pair<int,ll>>::iterator it = myset.upper_bound(val);
    if(it == myset.begin()) 
      myset.insert(val);
    else {
      it--;
      if(val.second < it->second)
        myset.insert(val);
    }
    it = myset.upper_bound(val);
    while(it != myset.end() && val.second <= it->second)
      myset.erase(it++);
  }
  ll extract(int wall) {
    std::set<std::pair<int,ll>>::iterator it = myset.lower_bound({wall + 1, -inf});
    assert(it != myset.begin());
    it--;
    return it->second + offset;
  }
  int size() {
    return myset.size();
  }
  void absorb(SpecialSet oth) {
    std::set<std::pair<int, ll>>::iterator it = oth.myset.begin();
    while(it != oth.myset.end()) {
      _insert({it->first, it->second + oth.offset});
      it++;
    }
  }
  void print() {
    std::cout << "Print\n";
    for(std::set<std::pair<int, ll>>::iterator it = myset.begin(); it != myset.end(); it++)
      std::cout << it->first << " " << it->second + offset << '\n';
    std::cout << '\n';
  }
};

int n;
std::vector<int> v;

void divide(int from, int to, SegmentTree &aint, SpecialSet &myset) {
  if(from == to) {
    ll result = 0;
    for(int h = 0; h < event[from].size(); h++)
      result += event[from][h].second;
    myset._insert({0, result});
    for(int h = 0; h < event[from].size(); h++) 
      myset._insert({event[from][h].first, result - event[from][h].second});
   
  } else {
    int mid = aint.query(1, 1, n, from, to).second;
    int target = v[mid];
    if(mid == to) 
      mid--;
    SpecialSet myset1, myset2;
    divide(from, mid, aint, myset1);
    divide(mid + 1, to, aint, myset2);
    ll upper1 = myset2.extract(target), upper2 = myset1.extract(target);
    myset1.update(upper1);
    myset2.update(upper2);

    if(myset1.size() < myset2.size())
      std::swap(myset1, myset2);
    myset1.absorb(myset2);
    std::swap(myset, myset1);
  }
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
  std::cin >> n;
  event.resize(1 + n);

  v = std::vector<int>(1 + n);
  for(int i = 1;i <= n; i++)
    std::cin >> v[i];
  int q;
  std::cin >> q;
  SegmentTree aint(n);
  aint.build(1, 1, n, v);

  for(int i = 1;i <= q; i++) {
    int x, y, cost;
    std::cin >> x >> y >> cost;
    event[x].push_back({y, cost});
  }
  SpecialSet myset;
  divide(1, n, aint, myset);
  std::cout << myset.extract(n);
  return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'void divide(int, int, SegmentTree&, SpecialSet&)':
constellation3.cpp:106:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int h = 0; h < event[from].size(); h++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~
constellation3.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int h = 0; h < event[from].size(); h++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65