Mai intai trebuie sa te autentifici.
Cod sursa(job #1657856)
Utilizator | Data | 20 martie 2016 20:50:14 | |
---|---|---|---|
Problema | Zeap | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.86 kb |
#include <fstream>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#define nmax 300005
#define inf 1<<30
using namespace std;
ifstream f("zeap.in");
ofstream g("zeap.out");
set <int> se;
map <int , int > mapi;
int n,m,poz,a[nmax];
char s[20];
struct element{
bool ok;
int mi,ma;
int difmin,difmax;};
element v[nmax*5];
int modul(int x)
{
if (x<0)
return -x;
return x;
}
void update(int nod,int st,int dr,bool val)
{
if (st==dr) {
v[nod].mi=a[st];
v[nod].ma=a[st];
v[nod].difmin=inf;
v[nod].difmax=-inf;
v[nod].ok=val;
return;
}
int mid=(st+dr)>>1;
v[nod].ok=true;
if (poz<=mid) update(nod*2,st,mid,val);
if (poz>mid) update(nod*2+1,mid+1,dr,val);
v[nod].mi=inf;
v[nod].ma=-inf;
v[nod].difmin=inf;
v[nod].difmax=-inf;
if (v[nod*2].ok==true) {
v[nod].mi=min(v[nod].mi,v[nod*2].mi);
v[nod].ma=max(v[nod].ma,v[nod*2].ma);
}
if (v[nod*2+1].ok==true) {
v[nod].mi=min(v[nod].mi,v[nod*2+1].mi);
v[nod].ma=max(v[nod].ma,v[nod*2+1].ma);
}
if (v[nod].ma==v[nod].mi)
v[nod].difmax=-inf;
else
v[nod].difmax=modul(v[nod].ma-v[nod].mi);
if (v[nod].ma==v[nod].mi) {
v[nod].difmin=inf;
return;
}
if (v[nod*2].ok==true)
v[nod].difmin=min(v[nod].difmin,modul(v[nod*2].difmin));
if (v[nod*2+1].ok==true)
v[nod].difmin=min(v[nod].difmin,modul(v[nod*2+1].difmin));
if (v[nod*2].ok==true&&v[nod*2+1].ok==true) {
v[nod].difmin=min(v[nod].difmin,modul(v[nod*2].ma-v[nod*2+1].ma));
v[nod].difmin=min(v[nod].difmin,modul(v[nod*2].mi-v[nod*2+1].mi));
}
}
void solve()
{
if (strcmp(s,"MIN")==0){
if (v[1].difmin==inf)
g<<-1<<'\n';
else
g<<v[1].difmin<<'\n';
return;
}
if (strcmp(s,"MAX")==0){
if (v[1].difmax==-inf)
g<<-1<<'\n';
else
g<<v[1].difmax<<'\n';
return;
}
int x=0;
for (int i=2;i<m;i++)
x=x*10+s[i]-'0';
if (s[0]=='C') {
g<<se.count(x)<<'\n';
return;
}
if (s[0]=='I') {
if (se.count(x)!=0)
return;
a[++n]=x;
se.insert(x);
mapi[x]=n;
poz=n;
update(1,1,nmax-5,true);
return;
}
if (s[0]=='S') {
if (se.count(x)==0) {
g<<-1<<'\n';
return;
}
poz=mapi[x];
a[poz]=0;
se.erase(x);
mapi.erase(x);
update(1,1,nmax-5,false);
}
}
int main()
{
int i,j;
while (1) {
f.getline(s,20);
m=strlen(s);
if (m==0)
break;
solve();
}
return 0;
}