Submission #65284760

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXNODE = 10000000;
struct Node{ Node *l,*r; int cnt; ll s0,s1; } pool[MAXNODE];
int ptr;
Node* newNode(){ Node* t=&pool[ptr++]; t->l=t->r=nullptr; t->cnt=0; t->s0=t->s1=0; return t; }
void upd(Node*& t,int lo,int hi,int x){
    if(!t) t=newNode();
    if(lo+1==hi){
        bool odd=!(t->cnt&1);
        t->cnt++;
        if(odd) t->s0+=x; else t->s1+=x;
        return;
    }
    int mid=lo+((hi-lo)>>1);
    if(x<mid) upd(t->l,lo,mid,x);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXNODE = 10000000;

struct Node{ Node *l,*r; int cnt; ll s0,s1; } pool[MAXNODE];
int ptr;

Node* newNode(){ Node* t=&pool[ptr++]; t->l=t->r=nullptr; t->cnt=0; t->s0=t->s1=0; return t; }

void upd(Node*& t,int lo,int hi,int x){
    if(!t) t=newNode();
    if(lo+1==hi){
        bool odd=!(t->cnt&1);
        t->cnt++;
        if(odd) t->s0+=x; else t->s1+=x;
        return;
    }
    int mid=lo+((hi-lo)>>1);
    if(x<mid) upd(t->l,lo,mid,x);
    else       upd(t->r,mid,hi,x);
    int cL=t->l?t->l->cnt:0, cR=t->r?t->r->cnt:0;
    ll s0L=t->l?t->l->s0:0, s1L=t->l?t->l->s1:0;
    ll s0R=t->r?t->r->s0:0, s1R=t->r?t->r->s1:0;
    t->cnt=cL+cR;
    if(!(cL&1)){ t->s0=s0L+s0R; t->s1=s1L+s1R; }
    else        { t->s0=s0L+s1R; t->s1=s1L+s0R; }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int Q; cin>>Q;
    Node* root=nullptr;
    ll z=0;
    
    while(Q--){
        ll y; cin>>y;
        int x=int((y+z)%1000000000)+1;
        upd(root,1,1000000001,x);
        z=root->s0;
        cout<<z<<"\n";
    }
    return 0;
}

Submission Info

Judge Result