oj.uz

Submission #234802

# Submission time Handle Problem Language Result Execution time Memory
234802 2020-05-25T16:55:59 Z AlexLuchianov Two Antennas (JOI19_antennas) C++14
22 / 100
 618 ms 25836 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

int const nmax = 200000;
int const inf = 1000000005;

struct El{
  int h;
  int a;
  int b;
} v[1 + nmax];
int _queries[1 + nmax][2];
int sol[1 + nmax];

vector<int> events[1 + nmax];
vector<pair<int,int>> queries[1 + nmax];

class SegmentTree{
private:
  struct Node{
    int result;
    int smax;
    Node operator + (Node const &a) const {
      return {max(result, a.result), max(smax, a.smax)};
    }
  };
public:
  vector<Node> aint;
  vector<int> lazy;

  SegmentTree(int n){
    aint.resize(1 + 4 * n);
    lazy.resize(1 + 4 * n);
  }

  void build(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      build(node * 2, from, mid);
      build(node * 2 + 1, mid + 1, to);
    }
    aint[node] = {-inf, -inf};
  }

  void cleannode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      lazy[node * 2] = max(lazy[node * 2], lazy[node]);
      lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
    }
    aint[node].result = max(aint[node].result, aint[node].smax + lazy[node]);
    lazy[node] = 0;
  }

  void computenode(int node, int from, int to){
    if(from < to){
      int mid = (from + to) / 2;
      aint[node] = aint[node * 2] + aint[node * 2 + 1];
    }
  }

  void update(int node, int from, int to, int x, int y, int val){
    if(x == from && to == y){
      lazy[node] = max(lazy[node], val);
      cleannode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);
      if(x <= mid)
        update(node * 2, from, mid, x, MIN(y, mid), val);
      if(mid + 1 <= y)
        update(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y, val);
      computenode(node, from, to);
    }
  }

  void setvalue(int node, int from, int to, int x, int val){
    if(from < to){
      int mid = (from + to) / 2;
      cleannode(node * 2, from, mid);
      cleannode(node * 2 + 1, mid + 1, to);
      if(x <= mid)
        setvalue(node * 2, from, mid, x, val);
      else
        setvalue(node * 2 + 1, mid + 1, to, x, val);
      computenode(node, from, to);
    } else {
      cleannode(node, from, to);
      aint[node].smax = val;
    }
  }

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

void solve(int n, int q){
  for(int i = 1;i <= n; i++) {
    events[i].clear();
    queries[i].clear();
  }

  for(int i = 1; i <= n; i++) {
    if(i + v[i].a <= n)
      events[i + v[i].a].push_back(i);
    if(i + v[i].b + 1 <= n)
      events[i + v[i].b + 1].push_back(-i);
  }

  for(int i = 1; i <= q; i++)
    queries[_queries[i][1]].push_back({_queries[i][0], i});
  SegmentTree aint(1 + n);

  for(int i = 1; i <= n; i++)
    aint.setvalue(1, 1, n, i, -inf);

  for(int i = 1; i <= n; i++){
    for(int h = 0; h < events[i].size(); h++){
      int id = events[i][h];
      if(0 < id)
        aint.setvalue(1, 1, n, id, -v[id].h);
      else
        aint.setvalue(1, 1, n, -id, -inf);
    }

    int x = max(1, i - v[i].b);
    int y = i - v[i].a;
    if(x <= y)
      aint.update(1, 1, n, x, y, v[i].h);


    for(int h = 0; h < queries[i].size(); h++){
      int pos = queries[i][h].second;
      sol[pos] = max(sol[pos], aint.query(1, 1, n, queries[i][h].first, i));
    }
  }
}

int oth(int n, int pos){
  return n - pos + 1;
}

int main()
{

  ios::sync_with_stdio(0);
  cin.tie(0);


  int n;
  cin >> n;
  for(int i = 1;i <= n; i++)
    cin >> v[i].h >> v[i].a >> v[i].b;
  int q;
  cin >> q;
  for(int i = 1;i <= q; i++)
    cin >> _queries[i][0] >> _queries[i][1];
  for(int i = 1;i <= q; i++)
    sol[i] = -1;

  solve(n, q);

  for(int i = 1;i <= n; i++)
    if(i < oth(n, i))
      swap(v[i], v[oth(n, i)]);
  for(int i = 1;i <= q; i++) {
    _queries[i][0] = oth(n, _queries[i][0]);
    _queries[i][1] = oth(n, _queries[i][1]);
    swap(_queries[i][0], _queries[i][1]);
  }

  solve(n, q);
  for(int i = 1;i <= q; i++)
    cout << sol[i] << '\n';

  return 0;
}

Compilation message

antennas.cpp: In member function 'void SegmentTree::cleannode(int, int, int)':
antennas.cpp:54:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~
antennas.cpp: In member function 'void SegmentTree::computenode(int, int, int)':
antennas.cpp:64:11: warning: unused variable 'mid' [-Wunused-variable]
       int mid = (from + to) / 2;
           ^~~
antennas.cpp: In function 'void solve(int, int)':
antennas.cpp:138:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < events[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~
antennas.cpp:152:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < queries[i].size(); h++){
                    ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 24068 KB Output is correct
2 Correct 582 ms 25628 KB Output is correct
3 Correct 385 ms 20924 KB Output is correct
4 Correct 592 ms 25836 KB Output is correct
5 Correct 246 ms 17140 KB Output is correct
6 Correct 587 ms 25684 KB Output is correct
7 Correct 507 ms 23572 KB Output is correct
8 Correct 618 ms 25756 KB Output is correct
9 Correct 84 ms 12200 KB Output is correct
10 Correct 575 ms 25556 KB Output is correct
11 Correct 346 ms 19896 KB Output is correct
12 Correct 590 ms 25656 KB Output is correct
13 Correct 505 ms 24872 KB Output is correct
14 Correct 481 ms 24272 KB Output is correct
15 Correct 466 ms 23700 KB Output is correct
16 Correct 461 ms 23672 KB Output is correct
17 Correct 508 ms 25136 KB Output is correct
18 Correct 475 ms 24160 KB Output is correct
19 Correct 494 ms 24224 KB Output is correct
20 Correct 483 ms 24340 KB Output is correct
21 Correct 463 ms 24800 KB Output is correct
22 Correct 486 ms 24608 KB Output is correct
23 Correct 474 ms 24664 KB Output is correct
24 Correct 450 ms 23528 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 9856 KB Output isn't correct
2 Halted 0 ms 0 KB -