oj.uz

Submission #1075271

# Submission time Handle Problem Language Result Execution time Memory
1075271 2024-08-25T23:00:55 Z raduv Simple (info1cup19_simple) C++17
100 / 100
 269 ms 39592 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200'001;
const long long INF = (1LL << 60);
struct aintnode{
  long long minimp, minpar, maximp, maxpar;
}aint[4 * MAXN + 1];
long long lazy[4 * MAXN + 1];
long long minipar, maximpar;
static inline void nodeupd(int node, long long val){
  if(aint[node].minpar != INF){
    aint[node].minpar += val;
    aint[node].maxpar += val;
  }
  if(aint[node].minimp != INF){
    aint[node].minimp += val;
    aint[node].maximp += val;
  }
  if(val % 2 == 1){
    swap(aint[node].minimp, aint[node].minpar);
    swap(aint[node].maximp, aint[node].maxpar);
  }
}
static inline void propagate(int node){
  if(lazy[node] > 0){
    lazy[2 * node] += lazy[node];
    nodeupd(2 * node, lazy[node]);
    lazy[2 * node + 1] += lazy[node];
    nodeupd(2 * node + 1, lazy[node]);
    lazy[node] = 0;
  }
}
void build(int node, int st, int dr){
  if(st == dr){
    int x;
    scanf("%d", &x);
    if(x % 2 == 0)
      aint[node].minpar = aint[node].maxpar = x;
    else
      aint[node].minimp = aint[node].maximp = x;
  }
  else{
    int mij = (st + dr) / 2;
    build(2 * node, st, mij);
    build(2 * node + 1, mij + 1, dr);
    aint[node].minpar = min(aint[2 * node].minpar, aint[2 * node + 1].minpar);
    aint[node].minimp = min(aint[2 * node].minimp, aint[2 * node + 1].minimp);
    aint[node].maxpar = max(aint[2 * node].maxpar, aint[2 * node + 1].maxpar);
    aint[node].maximp = max(aint[2 * node].maximp, aint[2 * node + 1].maximp);
  }
}
void update(int node, int st, int dr, int l, int r, int val){
  if( l <= st && dr <= r ){
    lazy[node] += val;
    nodeupd(node, val);
  }
  else{
    propagate(node);
    int mij = (st + dr) / 2;
    if( l <= mij )
      update(2 * node, st, mij, l, r, val);
    if(r > mij)
      update(2 * node + 1, mij + 1, dr, l, r, val);
    aint[node].minpar = min(aint[2 * node].minpar, aint[2 * node + 1].minpar);
    aint[node].minimp = min(aint[2 * node].minimp, aint[2 * node + 1].minimp);
    aint[node].maxpar = max(aint[2 * node].maxpar, aint[2 * node + 1].maxpar);
    aint[node].maximp = max(aint[2 * node].maximp, aint[2 * node + 1].maximp);
  }
}
void query(int node, int st, int dr, int l, int r){
  if( l <= st && dr <= r ){
    minipar = min(minipar, aint[node].minpar);
    maximpar = max(maximpar, aint[node].maximp);
  }
  else{
    propagate(node);
    int mij = (st + dr) / 2;
    if( l <= mij )
      query(2 * node, st, mij, l, r);
    if(r > mij)
      query(2 * node + 1, mij + 1, dr, l, r);
  }
}
int main() {
  int n, q, i, l, r, val, tip;
  scanf("%d", &n);
  for( i = 0; i <= 4 * MAXN; i++ ){
    aint[i].minimp = aint[i].minpar = INF;
    aint[i].maximp = aint[i].maxpar = -1;
  }
  build(1, 1, n);
 
 
  scanf("%d", &q);
  for( i = 0; i < q; i++ ){
    scanf("%d%d%d", &tip, &l, &r);
    if(tip == 0){
      scanf("%d", &val);
      update(1, 1, n, l, r, val);
    }
    else{
      minipar = INF;
      maximpar = -1;
      query(1, 1, n, l, r);
      printf("%lld %lld\n", (minipar == INF ? -1 : minipar), maximpar);
    }
  }
  return 0;
}

Compilation message

subway.cpp: In function 'void build(int, int, int)':
subway.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d", &x);
      |     ~~~~~^~~~~~~~~~
subway.cpp: In function 'int main()':
subway.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
subway.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
subway.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d%d%d", &tip, &l, &r);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
subway.cpp:98:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |       scanf("%d", &val);
      |       ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25692 KB Output is correct
2 Correct 12 ms 25600 KB Output is correct
3 Correct 14 ms 25692 KB Output is correct
4 Correct 16 ms 25692 KB Output is correct
5 Correct 15 ms 25692 KB Output is correct
6 Correct 12 ms 25612 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 28776 KB Output is correct
2 Correct 152 ms 33616 KB Output is correct
3 Correct 149 ms 33620 KB Output is correct
4 Correct 164 ms 33648 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25692 KB Output is correct
2 Correct 12 ms 25600 KB Output is correct
3 Correct 14 ms 25692 KB Output is correct
4 Correct 16 ms 25692 KB Output is correct
5 Correct 15 ms 25692 KB Output is correct
6 Correct 12 ms 25612 KB Output is correct
7 Correct 90 ms 28776 KB Output is correct
8 Correct 152 ms 33616 KB Output is correct
9 Correct 149 ms 33620 KB Output is correct
10 Correct 164 ms 33648 KB Output is correct
11 Correct 100 ms 32160 KB Output is correct
12 Correct 234 ms 38484 KB Output is correct
13 Correct 212 ms 39300 KB Output is correct
14 Correct 269 ms 38532 KB Output is correct
15 Correct 191 ms 39592 KB Output is correct
16 Correct 68 ms 31828 KB Output is correct