Submission #201862

#	Time	Username	Problem	Language	Result	Execution time	Memory
201862		theStaticMind	Two Antennas (JOI19_antennas)	C++14	24 / 100	3068 ms	43136 KiB

antennas

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> segn, segx;
int S;
int get(int a, int b, bool mx){
      return (mx ? max(a, b) : min(a, b));
}
void build(vector<int>& seg, bool mx){
      S = (1ll << (int)ceil(log2(seg.size())));
      int l = S - seg.size();
      for(int i = 0; i < l; i++)seg.pb(mx?0:INF);
      reverse(all(seg));
      for(int i = 1; i < seg.size(); i += 2) seg.pb(get(seg[i - 1], seg[i], mx));
      seg.pb('a' + 't' + 'a' + 'k' + 'a' + 'n');
      reverse(all(seg));
}

int query(vector<int>& seg, int j, int a, int b, int x, int y, bool mx){
      if(y < a || b < x) return(mx ? 0 : INF);
      if(a <= x && y <= b) return seg[j];
      return  get(query(seg, j * 2, a, b, x, (x + y) / 2, mx), query(seg, j * 2 + 1, a ,b, (x + y) / 2 + 1, y, mx), mx);
}
void update(vector<int>& seg, int j, int v,bool mx){
      seg[j] = v;
      j /= 2;
      while(j > 0){
            seg[j] = get(seg[j * 2], seg[j * 2 + 1], mx);
            j /= 2;
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n;
      cin >> n;
      vector<int> H(n + 1);
      vector<int> A(n + 1);
      vector<int> B(n+ 1);
      vector<int> sweep[3 * n];
      set<int> curr;
      for(int i = 1; i <= n; i++){
            cin >> H[i] >> A[i] >> B[i];
            sweep[i + A[i]].pb(i);
            sweep[i + B[i]].pb(-i);
      }

      segn = vector<int>(n + 1, INF);
      segx = vector<int>(n + 1, 0);
      build(segx, true);
      build(segn, false);

      int q;
      cin >> q;
      vector<int> ans(q + 2, -1);
      vector<int> qq(q + 2);
      vector<int> Q[n + 2];
      for(int i = 1; i <= q; i++){
            int l, r;
            cin >> l >> r;
            Q[l].pb(i);
            Q[r + 1].pb(-i);
            qq[i] = l;
      }
      for(int i = 1; i <= n; i++){
            for(int j = 0; j < sweep[i].size(); j++){
                  int id = sweep[i][j];
                  if(id > 0){
                        update(segx, segx.size() - S + id, H[id], true);
                        update(segn, segn.size() - S + id, H[id], false);
                  }
            }
            for(int j = 0; j < Q[i].size(); j++){
                  int id = Q[i][j];
                  if(id > 0){
                        curr.insert(id);
                  }
                  else {
                        curr.erase(-id);
                  }
            }
            for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
                  ans[*itr] = max(ans[*itr],
                      max(
                          query(segx, 1, max(i - B[i], qq[*itr]), i - A[i], 0, S - 1, true) - H[i] ,
                          H[i] - query(segn, 1, max(i - B[i], qq[*itr]), i - A[i], 0, S - 1, false)
                          )
                      );
            }

            for(int j = 0; j < sweep[i].size(); j++){
                  int id = sweep[i][j];
                  if(id < 0){
                        id = -id;
                        update(segx, segx.size() - S + id, 0, true);
                        update(segn, segn.size() - S + id, INF, false);
                  }
            }

      }
      for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

antennas.cpp: In function 'void build(std::vector<long long int>&, bool)':
antennas.cpp:22:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 1; i < seg.size(); i += 2) seg.pb(get(seg[i - 1], seg[i], mx));
                      ~~^~~~~~~~~~~~
antennas.cpp: In function 'int32_t main()':
antennas.cpp:76:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < sweep[i].size(); j++){
                            ~~^~~~~~~~~~~~~~~~~
antennas.cpp:83:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < Q[i].size(); j++){
                            ~~^~~~~~~~~~~~~
antennas.cpp:101:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < sweep[i].size(); j++){
                            ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 65