fork(2) download
copy 
  1. const
  2.   fi = '';
  3. var
  4.   a : array[1..50000] of longint;
  5.   val,valmax,rem : array[1..200000] of longint;
  6.   n,k,m : longint;
  7.  
  8.  
  9. procedure enter;
  10.   var
  11.     i,j,tmp : longint;
  12.   begin
  13.     n := 0;
  14.     readln(k,m);
  15.     i := 1;
  16.     for j := 1 to k do
  17.       begin
  18.         read(tmp);
  19.         a[i] := 1;
  20.         inc(i,tmp);
  21.         inc(n,tmp);
  22.       end;
  23.     readln;
  24.   end;
  25.  
  26. procedure init(s,l,r : longint);
  27.   var
  28.     mid : longint;
  29.   begin
  30.     if l = r then
  31.       begin
  32.         valmax[s] := 1;
  33.         exit;
  34.       end;
  35.     mid := (l + r) div 2;
  36.     init(2*s,l,mid);
  37.     init(2*s+1,mid+1,r);
  38.     valmax[s] := valmax[2*s] + valmax[2*s+1];
  39.   end;
  40.  
  41. procedure init2(s,l,r : longint);
  42.   var
  43.     mid : longint;
  44.   begin
  45.     if l = r then
  46.       begin
  47.         inc(val[s],a[l]);
  48.         exit;
  49.       end;
  50.     mid := (l + r) div 2;
  51.     init2(2*s,l,mid);
  52.     init2(2*s+1,mid+1,r);
  53.     val[s] := val[2*s] + val[2*s+1];
  54.   end;
  55.  
  56. procedure trans(s,l,r : longint);
  57.   var
  58.     mid : longint;
  59.   begin
  60.     if (s = 0) or (l = r) then exit;
  61.     mid := (l + r) div 2;
  62.     inc(val[2*s],rem[s]*(mid-l+1));
  63.     inc(val[2*s+1],rem[s]*(r-mid));
  64.     inc(rem[2*s],rem[s]);
  65.     inc(rem[2*s+1],rem[s]);
  66.     rem[s] := 0;
  67.   end;
  68.  
  69. procedure Jupdate(s,l,r,u,v : longint);
  70.   var
  71.     mid : longint;
  72.   begin
  73.     if (r < u) or (v < l) then exit;
  74.     if (u <= l) and (r <= v) then
  75.       begin
  76.         if val[s] = valmax[s] then
  77.           begin
  78.             dec(val[s],r-l+1);
  79.             dec(rem[s]);
  80.             exit;
  81.           end;
  82.         if val[s] = 0 then exit;
  83.       end;
  84.     trans(s,l,r);
  85.     mid := (l + r) div 2;
  86.     Jupdate(2*s,l,mid,u,v);
  87.     Jupdate(2*s+1,mid+1,r,u,v);
  88.     val[s] := val[2*s] + val[2*s+1];
  89.   end;
  90.  
  91. procedure Dupdate(s,l,r,u,v : longint);
  92.   var
  93.     mid : longint;
  94.   begin
  95.     if (r < u) or (v < l) then exit;
  96.     if (u <= l) and (r <= v) then
  97.       begin
  98.         if val[s] = 0 then
  99.           begin
  100.             inc(val[s],r-l+1);
  101.             inc(rem[s]);
  102.             exit;
  103.           end;
  104.         if val[s] = valmax[s] then exit;
  105.       end;
  106.     trans(s,l,r);
  107.     mid := (l + r) div 2;
  108.     Dupdate(2*s,l,mid,u,v);
  109.     Dupdate(2*s+1,mid+1,r,u,v);
  110.     val[s] := val[2*s] + val[2*s+1];
  111.   end;
  112.  
  113. procedure query(c : char; u,v : longint);
  114.   begin
  115.     if c = 'J' then Jupdate(1,1,n,u+1,v)
  116.     else Dupdate(1,1,n,u+1,v);
  117.   end;
  118.  
  119. procedure main;
  120.   var
  121.     i,u,v : longint;
  122.     c : char;
  123.   begin
  124.     init(1,1,n);
  125.     init2(1,1,n);
  126.     for i := 1 to m do
  127.       begin
  128.         read(c);
  129.         if c = 'C' then
  130.           begin
  131.             writeln(val[1]);
  132.             readln;
  133.           end
  134.         else
  135.           begin
  136.             readln(u,v);
  137.             query(c,u,v);
  138.           end;
  139.       end;
  140.   end;
  141.  
  142.  
  143. begin
  144.   assign(input,fi);
  145.   reset(input);
  146.   enter;
  147.   main;
  148.   close(input);
  149. end.
  150.  
Success #stdin #stdout 0s 2768KB
comments (?)
stdin
copy 
2 3
2 2
J 2 3
D 2 4
C
stdout
copy 
3
https://ideone.com/bnscUh
problem WS, based on SPOJ submission 16708871 (PAS fpc), 2016-04-10 08:20:43
language:
Pascal (fpc 3.0.4)
created:
8 years ago
visibility:
secret

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!