oj.uz

Submission #201862

# Submission time Handle Problem Language Result Execution time Memory
201862 2020-02-12T10:23:36 Z theStaticMind Two Antennas (JOI19_antennas) C++14
24 / 100
 3000 ms 43136 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];
      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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 9 ms 380 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 7 ms 376 KB Output is correct
18 Correct 7 ms 380 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 6 ms 376 KB Output is correct
21 Correct 7 ms 376 KB Output is correct
22 Correct 7 ms 376 KB Output is correct
23 Correct 6 ms 376 KB Output is correct
24 Correct 7 ms 376 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 9 ms 380 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 7 ms 376 KB Output is correct
18 Correct 7 ms 380 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 6 ms 376 KB Output is correct
21 Correct 7 ms 376 KB Output is correct
22 Correct 7 ms 376 KB Output is correct
23 Correct 6 ms 376 KB Output is correct
24 Correct 7 ms 376 KB Output is correct
25 Execution timed out 3068 ms 9892 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 39668 KB Output is correct
2 Correct 343 ms 43132 KB Output is correct
3 Correct 244 ms 32836 KB Output is correct
4 Correct 388 ms 43136 KB Output is correct
5 Correct 141 ms 20520 KB Output is correct
6 Correct 344 ms 43136 KB Output is correct
7 Correct 298 ms 38468 KB Output is correct
8 Correct 360 ms 43136 KB Output is correct
9 Correct 45 ms 6808 KB Output is correct
10 Correct 346 ms 43136 KB Output is correct
11 Correct 207 ms 26024 KB Output is correct
12 Correct 357 ms 43136 KB Output is correct
13 Correct 249 ms 40692 KB Output is correct
14 Correct 234 ms 40904 KB Output is correct
15 Correct 200 ms 40924 KB Output is correct
16 Correct 219 ms 42212 KB Output is correct
17 Correct 252 ms 40868 KB Output is correct
18 Correct 215 ms 40784 KB Output is correct
19 Correct 225 ms 40560 KB Output is correct
20 Correct 229 ms 40828 KB Output is correct
21 Correct 241 ms 40300 KB Output is correct
22 Correct 227 ms 40688 KB Output is correct
23 Correct 230 ms 40696 KB Output is correct
24 Correct 222 ms 41336 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 8 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 9 ms 380 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 8 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 8 ms 376 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 6 ms 376 KB Output is correct
17 Correct 7 ms 376 KB Output is correct
18 Correct 7 ms 380 KB Output is correct
19 Correct 5 ms 376 KB Output is correct
20 Correct 6 ms 376 KB Output is correct
21 Correct 7 ms 376 KB Output is correct
22 Correct 7 ms 376 KB Output is correct
23 Correct 6 ms 376 KB Output is correct
24 Correct 7 ms 376 KB Output is correct
25 Execution timed out 3068 ms 9892 KB Time limit exceeded
26 Halted 0 ms 0 KB -