| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 797022 | Shithila | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9;
int main()
{
int q;
cin>>q;
vector<int> num;
vector<int> temp;
map<int,int> chek;
vector<int> prefix(q);
int y=0;
int bloksize=sqrt(q);
for(int ll=0;ll<q;ll++)
{
char com;
cin>>com;
if(com=='+')
{
int n;
cin>>n;
if(chek.find((y+n)%mod)==chek.end())
{
temp.push_back((y+n)%mod);
chek[(y+n)%mod]=true;
}
}
y=0;
if(com=='?')
{
int l;
int r;
cin>>l>>r;
for(int i=0;i<temp.size();i++)
{
if(temp[i]<=r && temp[i]>=l)
{
y=y+temp[i];
}
}
int left=0;
int right=num.size()-1;
int leftans=-1;
int rightans=-1;
while(left<=right)
{
int mid=left+right;
mid=mid/2;
if(num[mid]<=r)
{
rightans=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
left=0;
right=num.size()-1;
while(left<=right)
{
int mid=left+right;
mid=mid/2;
if(num[mid]>=l)
{
leftans=mid;
right=mid-1;
}
else
{
left=mid+1;
}
}
if(rightans==-1) y=y;
else if(leftans==0) y=y+prefix[rightans];
else y=y+prefix[rightans]-prefix[leftans-1];
cout<<y<<endl;
}
if(temp.size()>=bloksize)
{
while(temp.empty()!=true)
{
num.push_back(temp.back());
temp.pop_back();
}
sort(num.begin(),num.end());
for(int i=0;i<num.size();i++)
{
if(i!=0 ) prefix[i]=prefix[i-1]+num[i];
else prefix[i]=num[i];
}
}
}
}