oj.uz

Submission #201854

# Submission time Handle Problem Language Result Execution time Memory
201854 2020-02-12T09:08:05 Z theStaticMind Two Antennas (JOI19_antennas) C++14
22 / 100
 378 ms 57220 KB 
#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];
      vector<int> Q[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, ans = -1;
      cin >> q;
      for(int i = 1; i <= q; i++){
            int l, r;
            cin >> l >> r;
            Q[l].pb(i);
            Q[r].pb(-i);
      }
      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);
                  }
            }
            ans = max(ans,
                      max(
                          query(segx, 1, i - B[i], i - A[i], 0, S - 1, true) - H[i] ,
                          H[i] - query(segn, 1, i - B[i], 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);
                  }
            }

      }
      cout << ans;
}

Compilation message

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:73:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < sweep[i].size(); j++){
                            ~~^~~~~~~~~~~~~~~~~
antennas.cpp:86:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < sweep[i].size(); j++){
                            ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 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 352 ms 52240 KB Output is correct
2 Correct 368 ms 57088 KB Output is correct
3 Correct 254 ms 42568 KB Output is correct
4 Correct 350 ms 57140 KB Output is correct
5 Correct 165 ms 26752 KB Output is correct
6 Correct 378 ms 57220 KB Output is correct
7 Correct 325 ms 50744 KB Output is correct
8 Correct 354 ms 56960 KB Output is correct
9 Correct 43 ms 8984 KB Output is correct
10 Correct 354 ms 57084 KB Output is correct
11 Correct 200 ms 34724 KB Output is correct
12 Correct 370 ms 57012 KB Output is correct
13 Correct 244 ms 54516 KB Output is correct
14 Correct 234 ms 54728 KB Output is correct
15 Correct 222 ms 54748 KB Output is correct
16 Correct 247 ms 56012 KB Output is correct
17 Correct 246 ms 54520 KB Output is correct
18 Correct 237 ms 54736 KB Output is correct
19 Correct 240 ms 54512 KB Output is correct
20 Correct 245 ms 54512 KB Output is correct
21 Correct 232 ms 54252 KB Output is correct
22 Correct 237 ms 54384 KB Output is correct
23 Correct 241 ms 54776 KB Output is correct
24 Correct 228 ms 55196 KB Output is correct

Subtask #4
0 / 65.0

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