oj.uz

답안 #639160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
639160 2022-09-08T18:37:29 Z cadmiumsky Fire (JOI20_ho_t5) C++14
6 / 100
 739 ms 33292 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

//#define int ll

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

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

const int nmax = 2e5 + 5;

#define lsb(x) (x & -x)
#define int ll
struct AIB {
  int tree[nmax * 2];
  int offset, len;
  void init(int l, int r) {
    offset = -l + 1;
    len = r - l + 1;
    memset(tree, 0, sizeof(tree[0]) * (len + 1));
  }
  
  void upd(int x, int val) {
    x += offset;
    //cerr << "+ " << x << ' ' << val << '\n';
    while(x <= len)
      tree[x] += val,
      x += lsb(x);
  }
  
  int query(int x) {
    x += offset;
    int sum = 0;
    while(x > 0)
      sum += tree[x],
      x -= lsb(x);
    return sum;
  }
  int query(int l, int r) {
    //cerr << l + offset << ' ' << r + offset << '\n';
    return query(r) - query(l - 1);
  }
};
#undef int

namespace DS {
  AIB offset, firstd, secondd;
  
  namespace Updates {
    vector<tii> upd;
    void push(int x, int val, int l, int r) {
      upd.emplace_back(l, val, x);
      upd.emplace_back(r + 1, -val, x + (r + 1) - l);
    }
    void update(int t, int val, int x) {
      //cerr << "+ " << t << ' ' << val << ' ' << x << '\n';
      int coef = x - t;
      offset.upd(coef, -val * t);
      firstd.upd(coef, val);
      secondd.upd(coef, (-coef) * val);
    }
  }
  
  namespace Queries {
    int side;
    vector<tii> qs;
    void push(int l, int r, int t) {
      qs.emplace_back(t, l, r);
    }
    ll query(int t, int l, int r) {
      auto [right, mid, left] = tii{r, r - t, l - t};
      if(side == 1) { // Orizontal \\ partea superioara
	//cerr << t << ' ' << l << ' ' << r << '\t' << '*' << (t + 1) << '\n';
	return (ll)offset.query(left, mid) + (ll)firstd.query(left, mid) * (t + 1);
      }
      else if(side == -1) {
	if(mid == right) return 0;
	mid++;
	return (ll)offset.query(mid, right) + (ll)secondd.query(mid, right) + (ll)firstd.query(mid, right) * (right + 1);
      }
      else if(side == -2) {
	mid = l;
	return (ll)offset.query(left, mid) + (ll)secondd.query(left, mid) + (ll)firstd.query(left, mid) * mid;
      }
      assert(false);
      return 0;
    }
  }
  using namespace Queries;
  using namespace Updates;
  
  void init(int n) {
    vector<int> ind(qs.size());
    vector<ll> rez(qs.size(), 0);
    
    //side == 1
    Queries::side = 1;
    //
    offset.init(-n - 1, n + 1);
    firstd.init(-n - 1, n + 1);
    secondd.init(-n - 1, n + 1);
    
    iota(all(ind), 0);
    sort(all(ind), [&](int a, int b) { return qs[a] < qs[b]; });
    sort(all(upd));
    int ptr = 0;
    for(auto i : ind) {
      auto [t, l, r] = qs[i];
      while(ptr < upd.size() && get<0>(upd[ptr]) <= t) {
	auto [time, val, poz] = upd[ptr];
	Updates::update(time, val, poz);
	ptr++;
      }
      rez[i] = Queries::query(t, l, r);
    }
    
    
    //for(auto x : rez)
      //cout << x << ' ';
    //cout << '\n';
      
    
    //side == -1
    Queries::side = -1;
    //
    offset.init(-n - 1, n + 1);
    firstd.init(-n - 1, n + 1);
    secondd.init(-n - 1, n + 1);
    
    iota(all(ind), 0);
    sort(all(ind), [&](int a, int b) { return get<2>(qs[a]) < get<2>(qs[b]); });
    sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
    ptr = 0;
    for(auto i : ind) {
      auto [t, l, r] = qs[i];
      while(ptr < upd.size() && get<2>(upd[ptr]) <= r) {
	auto [time, val, poz] = upd[ptr];
	Updates::update(time, val, poz);
	ptr++;
      }
      rez[i] += Queries::query(t, l, r);
    }
    
    //for(auto x : rez)
      //cout << x << ' ';
    //cout << '\n';
    
    //side == -2
    Queries::side = -2;
    //
    offset.init(-n - 1, n + 1);
    firstd.init(-n - 1, n + 1);
    secondd.init(-n - 1, n + 1);
    
    iota(all(ind), 0);
    sort(all(ind), [&](int a, int b) { return get<1>(qs[a]) < get<1>(qs[b]); });
    sort(all(upd), [&](auto a, auto b) {return get<2>(a) < get<2>(b); });
    ptr = 0;
    for(auto i : ind) {
      auto [t, l, r] = qs[i];
      while(ptr < upd.size() && get<2>(upd[ptr]) <= l) {
	auto [time, val, poz] = upd[ptr];
	Updates::update(time, val, poz);
	ptr++;
      }
      rez[i] -= Queries::query(t, l, r);
    }
    
    
    
    for(auto x : rez)
      cout << x << ' ';
    cout << '\n';
      
    return;
  }
  
}

signed main() {
  int n, q;
  cin >> n >> q;
  vector<int> v(n);
  for(auto &x : v)
    cin >> x;
  vector<int> poz, rend;
  for(int i = n - 1; i >= 0; i--) {
    DS::Updates::push(i, v[i], 0, 0);
    int boundary = i;
    while(!poz.empty() && v[poz.back()] <= v[i]) {
      DS::Updates::push(poz.back(), v[i] - v[poz.back()], poz.back() - i, rend.back() - i);
      boundary = rend.back();
      poz.pop_back();
      rend.pop_back();
    }
    poz.emplace_back(i);
    rend.emplace_back(boundary);
  }
  
  for(int i = 0, t, l, r; i < q; i++) {
    cin >> t >> l >> r;
    --l;
    --r;
    DS::Queries::push(l, r, t);
  }
  
  DS::init(n);
  return 0;
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

Compilation message

ho_t5.cpp: In function 'll DS::Queries::query(int, int, int)':
ho_t5.cpp:76:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |       auto [right, mid, left] = tii{r, r - t, l - t};
      |            ^
ho_t5.cpp: In function 'void DS::init(int)':
ho_t5.cpp:113:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |       auto [t, l, r] = qs[i];
      |            ^
ho_t5.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |       while(ptr < upd.size() && get<0>(upd[ptr]) <= t) {
      |             ~~~~^~~~~~~~~~~~
ho_t5.cpp:115:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |  auto [time, val, poz] = upd[ptr];
      |       ^
ho_t5.cpp:140:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  140 |       auto [t, l, r] = qs[i];
      |            ^
ho_t5.cpp:141:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |       while(ptr < upd.size() && get<2>(upd[ptr]) <= r) {
      |             ~~~~^~~~~~~~~~~~
ho_t5.cpp:142:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  142 |  auto [time, val, poz] = upd[ptr];
      |       ^
ho_t5.cpp:165:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |       auto [t, l, r] = qs[i];
      |            ^
ho_t5.cpp:166:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |       while(ptr < upd.size() && get<2>(upd[ptr]) <= l) {
      |             ~~~~^~~~~~~~~~~~
ho_t5.cpp:167:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  167 |  auto [time, val, poz] = upd[ptr];
      |       ^

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 707 ms 33292 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 739 ms 32356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 606 ms 29728 KB Output is correct
2 Correct 630 ms 29852 KB Output is correct
3 Correct 615 ms 30592 KB Output is correct
4 Correct 597 ms 29728 KB Output is correct
5 Correct 612 ms 29860 KB Output is correct
6 Correct 647 ms 29904 KB Output is correct
7 Correct 606 ms 30440 KB Output is correct
8 Correct 608 ms 30220 KB Output is correct
9 Correct 614 ms 29944 KB Output is correct
10 Correct 586 ms 30112 KB Output is correct
11 Correct 631 ms 30088 KB Output is correct
12 Correct 594 ms 30140 KB Output is correct
13 Correct 597 ms 30012 KB Output is correct
14 Correct 586 ms 29976 KB Output is correct

Subtask #5
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 308 KB Output isn't correct
3 Halted 0 ms 0 KB -