Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <climits>
- using namespace std;
- long long int apples[100020],seg[200022],seg2[200022];
- long long int min (long long int a, long long int b){
- if(a<b) return a;
- return b;
- }
- void buildt(long long int start,long long int end,long long int node){
- if(start == end){
- seg[node] = apples[start];
- seg2[node] = apples[start];
- }
- else{
- long long int mid = (long long int) ((start + end) / 2);
- buildt( start, mid,(long long int)(2*node));
- buildt( (long long int)(mid+1), end,(long long int)((2*node)+1));
- seg[node] = seg[2*node] + seg[(2*node)+1];
- seg2[node] = min(seg2[2*node] , seg2[(2*node)+1]);
- }
- }
- void update(long long int node,long long int start,long long int end,long long int idx, long long int val)
- {
- if(start == end )
- {
- apples[idx] = (long long int) (apples[idx] + val);
- if(apples[idx] < 0){
- seg[node] = 0;
- seg2[node] = 0;
- }
- else{
- seg[node] = (long long int)(seg[node]+ val);
- seg2[node] = (long long int)(seg2[node] + val);
- }
- }
- else
- {
- long long int mid = (long long int) ((start + end) / 2);
- if(start <= idx && idx <= mid)
- update( (long long int)(2*node), start, mid, idx, val);
- else
- update((long long int)((2*node)+1), (long long int)(mid+1), end, idx, val);
- seg[node] = seg[2*node] + seg[(2*node)+1];
- seg2[node] = min(seg2[2*node] , seg2[(2*node)+1]);
- }
- }
- long long int querysum(long long int node, long long int start, long long int end,long long int l,long long int r)
- {
- if(r < start || end < l)
- {
- return 0;
- }
- if(l <= start && end <= r)
- return seg[node];
- long long int mid = (long long int) ((start + end) / 2);
- long long int p1 = querysum((long long int)(2*node), start, mid, l, r);
- long long int p2 = querysum((long long int)((2*node)+1), (long long int)(mid+1), end, l, r);
- return (p1 + p2);
- }
- long long int querymin(long long int node, long long int start, long long int end, long long int l, long long int r)
- {
- if(r < start || end < l)
- {
- return LLONG_MAX;
- }
- if(l <= start && end <= r)
- return seg2[node];
- long long int mid = (long long int) ((start + end) / 2);
- long long int p1 = querymin((long long int)(2*node), start, mid, l, r);
- long long int p2 = querymin((long long int)((2*node)+1), (long long int)(mid+1), end, l, r);
- return min(p1 , p2);
- }
- int main()
- {
- long long int n;
- cin >> n;
- for(int i = 1; i <= n; i++)
- cin >> apples[i];
- buildt(1,n,1);
- int op;
- cin >> op;
- string c;
- getline(cin,c);
- while(op--){
- cin >> c;
- char a1[64];
- char a2[64];
- cin >> a1 >> a2;
- if(c[0] == 'C')
- cout << querysum(1,1,n,(long long int)(atoll(a1)+1),(long long int)(atoll(a2)+1)) - querymin(1,1,n,(long long int)(atoll(a1)+1),(long long int)(atoll(a2)+1))<<endl;
- else
- if(c[0] == 'G')
- update(1,1,n,(long long int)(atoll(a2)+1),(long long int)(atoll(a1)));
- else
- update(1,1,n,(long long int)(atoll(a2)+1),(long long int)(-1*(atoll(a1))));
- }
- }
- if(start == end )
- {
- apples[idx] = (long long int) (apples[idx] + val);
- if(apples[idx] < 0){
- seg[node] = 0;
- seg2[node] = 0;
- }
- else{
- seg[node] = (long long int)(seg[node]+ val);
- seg2[node] = (long long int)(seg2[node] + val);
- }
- }
- if(start == end )
- {
- apples[idx] = (long long int) (apples[idx] + val);
- if(apples[idx] < 0){
- apples[idx]=0;
- seg[node] = 0;
- seg2[node] = 0;
- }
- else{
- seg[node] = (long long int)(seg[node]+ val);
- seg2[node] = (long long int)(seg2[node] + val);
- }
- }
- #include <iostream>
- #include <string>
- #include <climits>
- using namespace std;
- long long int apples[100020],seg[200022],seg2[200022];
- long long int min (long long int a, long long int b){
- if(a<b) return a;
- return b;
- }
- void buildt(long long int start,long long int end,long long int node){
- if(start == end){
- seg[node] = apples[start];
- seg2[node] = apples[start];
- }
- else{
- long long int mid = (long long int) ((start + end) / 2);
- buildt( start, mid,(long long int)(2*node));
- buildt( (long long int)(mid+1), end,(long long int)((2*node)+1));
- seg[node] = seg[2*node] + seg[(2*node)+1];
- seg2[node] = min(seg2[2*node] , seg2[(2*node)+1]);
- }
- }
- void update(long long int node,long long int start,long long int end,long long int idx, long long int val)
- {
- if(start == end )
- {
- apples[idx] = (long long int) (apples[idx] + val);
- if(apples[idx] < 0){
- apples[idx]=0;
- seg[node] = 0;
- seg2[node] = 0;
- }
- else{
- seg[node] = (long long int)(seg[node]+ val);
- seg2[node] = (long long int)(seg2[node] + val);
- }
- }
- else
- {
- long long int mid = (long long int) ((start + end) / 2);
- if(start <= idx && idx <= mid)
- update( (long long int)(2*node), start, mid, idx, val);
- else
- update((long long int)((2*node)+1), (long long int)(mid+1), end, idx, val);
- seg[node] = seg[2*node] + seg[(2*node)+1];
- seg2[node] = min(seg2[2*node] , seg2[(2*node)+1]);
- }
- }
- long long int querysum(long long int node, long long int start, long long int end,long long int l,long long int r)
- {
- if(r < start || end < l)
- {
- return 0;
- }
- if(l <= start && end <= r)
- return seg[node];
- long long int mid = (long long int) ((start + end) / 2);
- long long int p1 = querysum((long long int)(2*node), start, mid, l, r);
- long long int p2 = querysum((long long int)((2*node)+1), (long long int)(mid+1), end, l, r);
- return (p1 + p2);
- }
- long long int querymin(long long int node, long long int start, long long int end, long long int l, long long int r)
- {
- if(r < start || end < l)
- {
- return LLONG_MAX;
- }
- if(l <= start && end <= r)
- return seg2[node];
- long long int mid = (long long int) ((start + end) / 2);
- long long int p1 = querymin((long long int)(2*node), start, mid, l, r);
- long long int p2 = querymin((long long int)((2*node)+1), (long long int)(mid+1), end, l, r);
- return min(p1 , p2);
- }
- int main()
- {
- long long int n;
- cin >> n;
- for(int i = 1; i <= n; i++)
- cin >> apples[i];
- buildt(1,n,1);
- int op;
- cin >> op;
- string c;
- getline(cin,c);
- while(op--){
- cin >> c;
- long long a1,a2;
- cin >> a1 >> a2;
- if(c[0] == 'C')
- cout << querysum(1,1,n,a1+1,a2+1) - querymin(1,1,n,a1+1,a2+1)<<endl;
- else
- if(c[0] == 'G')
- update(1,1,n,a2+1,a1);
- else
- update(1,1,n,a2+1,0-a1);
- }
- }
Add Comment
Please, Sign In to add comment