# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
797087 | 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 n;
int m;
cin>>n>>m;
int arr[n];
int blocksize=350;
vector<int> cos((n/blocksize)+1);
vector<multiset<int> > chek((n/blocksize)+1);
for(int ll=0;ll<n;ll++)
{
cin>>arr[ll];
chek[ll/blocksize].insert(arr[ll]);
}
for(int ll=0;ll<m;ll++)
{
char com;
cin>>com;
if(com=='+')
{
int l;
int r;
int x;
cin>>l>>r>>x;
l--;
r--;
for(int i=l;i<=r;)
{
if(i%blocksize==0 && i+blocksize<r)
{
cos[i/blocksize]+=x;
i+=blocksize;
}
else
{
chek[i/blocksize].erase(chek[i/blocksize].find(arr[i]));
arr[i]=arr[i]+x;
chek[i/blocksize].insert(arr[i]);
i++;
}
}
}
else
{
int l;
int r;
int y;
cin>>l>>r>>y;
l--;
r--;
bool found=false;
for(int i=l;i<=r;)
{
if(i%blocksize==0 && i+blocksize<r)
{
if(chek[i/blocksize].find(y-cos[i/blocksize])!=chek[i/blocksize].end())
{
found=true;
}
i+=blocksize;
}
else
{
if(arr[i]+cos[i/blocksize]==y)
{
found=true;
}
i++;
}
}
if(found==true)
{
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
}
}