fork(1) download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. ifstream f("test.in");
  7. ofstream g("test.out");
  8.  
  9. #define nmax 100005
  10.  
  11. typedef struct{
  12.     int val, add, viz;
  13. }camp;
  14.  
  15. camp aint[nmax*4];
  16. int n, m, sum;
  17.  
  18. void udpate(int nod, int st, int dr, int a, int b, int val){
  19.  
  20.     if (a <= st && dr <= b){
  21.         aint[nod].val += val*(dr-st+1);
  22.         aint[nod].add += val;
  23.         aint[nod].viz = 1;
  24.         return;
  25.     }
  26.  
  27.     int mij = (st + dr) / 2;
  28.  
  29.     if (aint[nod].viz==1){
  30.         udpate(nod*2, st, mij, st, mij, aint[nod].add);
  31.         udpate(nod*2+1, mij+1, dr, mij+1, dr, aint[nod].add);
  32.         aint[nod].viz = 0;
  33.         aint[nod].add = 0;
  34.     }
  35.  
  36.     if (a <= mij) udpate(nod*2, st, mij, a, b, val);
  37.     if (b > mij) udpate(nod*2+1, mij+1, dr, a, b, val);
  38.  
  39.     aint[nod].val = aint[nod*2].val + aint[nod*2+1].val;
  40.  
  41. }
  42.  
  43. void citeste(){
  44.  
  45.     f >> n >> m;
  46.     for(int i=1; i<=n; i++){
  47.         int x;
  48.         f >> x;
  49.         udpate(1,1,n,i,i,x);
  50.     }
  51.  
  52. }
  53.  
  54. void query(int nod, int st, int dr, int a, int b){
  55.  
  56.     if (a <= st && dr <= b){
  57.         sum += aint[nod].val;
  58.         return;
  59.     }
  60.  
  61.     int mij = (st + dr) / 2;
  62.     if (aint[nod].viz == 1){
  63.         udpate(nod*2, st, mij, st, mij, aint[nod].add);
  64.         udpate(nod*2+1, mij+1, dr, mij+1, dr, aint[nod].add);
  65.         aint[nod].viz = 0;
  66.         aint[nod].add = 0;
  67.     }
  68.  
  69.     if (a <= mij) query(nod*2, st, mij, a, b);
  70.     if ( b > mij) query(nod*2+1, mij+1, dr, a, b);
  71.  
  72. }
  73.  
  74. int main(){
  75.  
  76.     citeste();
  77.     for(int i=1; i<=m; i++){
  78.         int x, y, x2, y2, val;
  79.         f >> x >> y >> x2 >> y2 >> val;
  80.         udpate(1,1,n,x,y,val);
  81.         sum = 0;
  82.         query(1,1,n,x2, y2);
  83.         g << sum << "\n";
  84.     }
  85.  
  86.     return 0;
  87.  
  88. }
  89.  
Success #stdin #stdout 0.02s 7500KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FmVovv
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!