T1 100:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll n,x,y,ans;
int main()
{
read(n),read(x),read(y);
for(int i=1;i<=n;++i)
{
ll a,b,c,d;
read(a),read(b),read(c),read(d);
a=max(a,(ll)0);
b=max(b,(ll)0);
c=max(c,(ll)0);
d=max(d,(ll)0);
a=min(a,x);
c=min(c,x);
b=min(b,y);
d=min(d,y);
ans+=(c-a)*(d-b);
}
cout<<ans;
return 0;
}
T2 100:
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
ll n,m,k,ans,l,r;
ll t[maxn],c[maxn];
bool check(ll x)
{
ll res=m;
for(int i=1;i<=n;++i)
{
ll v=t[i]-x;
if(v<=0) continue;
res-=v*c[i];
if(res<0) return false;
}
return true;
}
int main()
{
read(n),read(m),read(k),l=k;
for(int i=1;i<=n;++i) read(t[i]),read(c[i]),r=max(r,t[i]);
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans;
return 0;
}
T3 100:
#include<bits/stdc++.h>
#define maxn 2510
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,q;
int dn[maxn];
char s[maxn];
unordered_map<int,int> mp[maxn];
bitset<maxn> f(int l,int r)
{
if(s[l]=='&'||s[l]=='|')
{
int l1,r1,l2,r2;
l1=l+1,r1=l1;
int num=0;
while(r1<=r)
{
if(s[r1]=='(') num++;
if(s[r1]==')') num--;
if(num==0) break;
r1++;
}
l2=r1+1,r2=r;
if(s[l]=='&') return f(l1+1,r1-1)&f(l2+1,r2-1);
else return f(l1+1,r1-1)|f(l2+1,r2-1);
}
else
{
int pos;
for(int i=l;i<=r;++i)
if(!isdigit(s[i]))
pos=i;
int x=0,y=0;
for(int i=l;i<=pos-1;++i) x=s[i]-'0'+x*10;
for(int i=pos+1;i<=r;++i) y=s[i]-'0'+y*10;
bitset<maxn> b;
if(s[pos]==':')
{
for(int i=1;i<=n;++i)
{
if(!mp[i].count(x)) b[i]=0;
else
{
if(mp[i][x]==y) b[i]=1;
else b[i]=0;
}
}
}
else
{
for(int i=1;i<=n;++i)
{
if(!mp[i].count(x)) b[i]=0;
else
{
if(mp[i][x]!=y) b[i]=1;
else b[i]=0;
}
}
}
return b;
}
}
int main()
{
read(n);
for(int i=1;i<=n;++i)
{
read(dn[i]);
int num;
read(num);
while(num--)
{
int x,y;
read(x),read(y);
mp[i][x]=y;
}
}
read(q);
while(q--)
{
scanf("%s",s+1);
int len=strlen(s+1);
bitset<maxn> ans=f(1,len);
vector<int> v;
for(int i=1;i<=n;++i)
if(ans[i])
v.push_back(dn[i]);
sort(v.begin(),v.end());
for(int i=0;i<v.size();++i) printf("%d ",v[i]);
puts("");
}
return 0;
}
T4 60:
#include<bits/stdc++.h>
#define maxn
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m,q;
struct node
{
int id;
vector<int> l,r;
};
set<node> s;
bool operator < (const node &a,const node &b)
{
int siz=a.r.size();
for(int i=0;i<m;++i)
if(a.r[i]!=b.r[i])
return a.r[i]<b.r[i];
return false;
}
bool operator == (const node &a,const node &b)
{
return a.id==b.id&&a.l==b.l&&a.r==b.r;
}
vector<int> operator - (const vector<int> &a,const int &b)
{
vector<int> c=a;
for(int i=m-1;i>=0;--i)
{
if(c[i])
{
c[i]-=b;
return c;
}
else
{
c[i]+=16;
c[i]-=b;
}
}
return c;
}
vector<int> get(string str)
{
vector<int> v;
int len=str.size();
for(int i=0;i<len;i+=5)
{
int val=0;
for(int j=i;j<i+4;++j)
{
int x;
if(isdigit(str[j])) x=str[j]-'0';
else
{
if(str[j]=='a') x=10;
if(str[j]=='b') x=11;
if(str[j]=='c') x=12;
if(str[j]=='d') x=13;
if(str[j]=='e') x=14;
if(str[j]=='f') x=15;
}
val=val*16+x;
}
v.push_back(val);
}
return v;
}
vector<int> R()
{
string str;
cin>>str;
return get(str);
}
set<node>::iterator find(vector<int> &x)
{
return s.lower_bound((node){0,x,x});
}
void work1()
{
int x;
vector<int> l,r;
set<node>::iterator t1,t2,it;
read(x),l=R(),r=R();
t1=find(l),t2=find(r);
if(t1==s.end()&&t2==s.end())
{
puts("YES");
s.insert((node){x,l,r});
return;
}
if(r<(*t1).l)
{
puts("YES");
s.insert((node){x,l,r});
return;
}
if((*t1)==(*t2)&&!(l<(*t1).l))
{
puts("NO");
return;
}
vector<node> v;
for(set<node>::iterator it=t1;it!=s.end();++it)
{
if(it==s.end()) break;
if(x!=(*it).id)
{
puts("NO");
return;
}
v.push_back(*it);
if(it==t2) break;
}
for(int i=0;i<v.size();++i) s.erase(v[i]);
if(v[0].l<l) l=v[0].l;
if(r<v[v.size()-1].r) r=v[v.size()-1].r;
puts("YES");
node tmp=(node){x,l,r},ttmp;
s.insert(tmp);
it=find(r);
if(it!=s.begin())
{
t1=it,t1--;
if((*t1).r==tmp.l-1&&(*t1).id==x)
{
ttmp=(node){x,(*t1).l,tmp.r};
s.erase(t1),s.erase(tmp);
tmp=ttmp;
s.insert(tmp);
}
}
it=find(r);
t1=it,t1++;
if(t1!=s.end())
{
if(tmp.r==(*t1).l-1&&(*t1).id==x)
{
ttmp=(node){x,tmp.l,(*t1).r};
s.erase(t1),s.erase(tmp);
tmp=ttmp;
s.insert(tmp);
}
}
}
void work2()
{
vector<int> x;
x=R();
set<node>::iterator it;
it=find(x);
if(it==s.end())
{
puts("0");
return;
}
if(x<(*it).l)
{
puts("0");
return;
}
printf("%d\n",(*it).id);
}
void work3()
{
vector<int> l,r;
set<node>::iterator t1,t2;
l=R(),r=R();
t1=find(l),t2=find(r);
if(t1==s.end()||t2==s.end())
{
puts("0");
return;
}
if(t1!=t2)
{
puts("0");
return;
}
if(l<(*t1).l)
{
puts("0");
return;
}
printf("%d\n",(*t1).id);
}
int main()
{
read(n),read(q),m=n/16;
while(q--)
{
int opt;
read(opt);
if(opt==1) work1();
if(opt==2) work2();
if(opt==3) work3();
}
return 0;
}
T5 60:
#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long ll;
template<typename T> inline void read(T &x)
{
x=0;char c=getchar();bool flag=false;
while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
if(flag)x=-x;
}
int n,m;
ll ans;
int l[maxn],r[maxn],id[maxn];
set<pair<int,int> > s;
map<pair<int,int>,bool> mp;
bool vis[maxn],V[maxn],vis2[maxn];
ll calc(int R)
{
if(V[R]) return 0;
V[R]=true;
ll val=0;
for(int i=1;i<=m;++i) vis[i]=false;
for(int i=1;i<=n;++i) vis2[i]=false;
int pos=0,id=0,mx=0;
for(int i=1;i<=m;++i)
{
if(l[i]>pos&&r[i]==R)
{
pos=l[i];
id=i;
}
}
vis[id]=true;
vis2[pos]=true;
val++;
priority_queue<pair<int,int> > q;
for(int i=1;i<=m;++i)
{
if(vis[i]) continue;
if(r[i]<=R)
{
q.push(make_pair(l[i],r[i]));
}
}
while(!q.empty())
{
int l=q.top().first,r=q.top().second;
q.pop();
if(r>=pos-1&&l<pos)
{
pos=l;
if(!vis2[pos])
{
vis2[pos]=true;
val++;
}
}
}
return val;
}
int main()
{
read(n),read(m);
for(int i=1;i<=m;++i) read(l[i]),read(r[i]);
for(int i=1;i<=m;++i) ans+=calc(r[i]);
cout<<ans;
return 0;
}