//土地丈量
#include<iostream>
using namespace std;
long long n, a, b, x1, x2, y1, y2,ans=0;
long long my_max(loC++ng long t1, long long t2){
if(t1>t2)
return t1;
return t2;
}
long long my_min(long long t1, long long t2){
if(t1<t2)
return t1;
return t2;
}
int main(){
cin>>n>>a>>b;
for(int i=0;i<n;i++){
cin>>x1>>y1>>x2>>y2;//核心就是区域不重叠,考虑好下面边界公式就好
ans+=my_max(0, my_min(x2,a)-my_max(x1,0))*my_max(0,my_min(y2,b)-my_max(y1,0));
}
cout<<ans;
return 0;
}
//垦田计划//贪心+桶排序+连续和 O(n+max_ti)
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1E5+10;
#define ll long long
ll n,m,k,cost;
ll t,c,t_cnt[maxn],c_sufsum[maxn],maxt=0;
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>t>>c;
t_cnt[t]++;
c_sufsum[t]+=c;
maxt=max(maxt,t);
}
for(int i=maxt;i>k;i--){//后缀和,当第i天优化时, c_sufsum都是代价
c_sufsum[i-1]=c_sufsum[i]+c_sufsum[i-1];
}
int d;
for(d=maxt;d>k;d--){
cost+=c_sufsum[d]; //试图d天缩短为d-1天
if(cost>m){//失败,否则成功
break;
}
}
cout<<d;
return 0;
}
//垦田计划////二分答案O(nlogn)
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1E5+10;
int n,m,k;
struct Land{
int t,c;
bool operator <(const Land l2)const{
return t==l2.t? c<l2.c:t<l2.t;//其实这个排序不必要,因为Σ(ti-anser)*ci的值不会因为这个排序而能单调贪心
}
}land[maxn];
bool check(int d){
int cost=0;
for(int i=n;i>=1&&land[i].t>d;i--){
cost+=(land[i].t-d)*land[i].c;
if(cost>m) return false;
}
return true;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>land[i].t>>land[i].c;
}
sort(land+1, land+n+1);
int l=k,r=land[n].t;//分析边界,最少只能缩短为k天,最多则是最长的天数 ,二分
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid;
}else{
l=mid+1;
}
}
cout<<l;
return 0;
}
//矩阵运算,softmax做矩阵运算时考虑运算量优化,另外数据量分析才知ll足够
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1E4+10, maxd=22;
ll n,d,q[maxn][maxd],k[maxd][maxn],v[maxn][maxd],w[maxn];
ll t[maxd][maxd],ans[maxn][maxd];//如果先算QK转置则二维数组存不下[maxn][maxn]规模的中间结果了
int main(){
cin>>n>>d;
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
cin>>q[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
cin>>k[j][i];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<d;j++){
cin>>v[i][j];
}
}
for(int i=0;i<n;i++){
cin>>w[i];
}
for(int ki=0;ki<d;ki++){//K×V
for(int vj=0;vj<d;vj++)
for(int kj=0;kj<n;kj++){//kj也是vi
t[ki][vj]+=k[ki][kj]*v[kj][vj];
}
}
for(int qi=0;qi<n;qi++){//W.Q
for(int qj=0;qj<d;qj++){
q[qi][qj]*=w[qi];
}
}
for(int qi=0;qi<n;qi++){//正好点乘和叉乘都满足乘法交换律,所以优化为(W.Q)×(K×V),时间复杂度O(nd^2)
for(int tj=0;tj<d;tj++){
for(int qj=0;qj<d;qj++){//qj也是ti
ans[qi][tj]+=q[qi][qj]*t[qj][tj];
}
}
}
for(int qi=0;qi<n;qi++){
for(int qj=0;qj<d;qj++){
cout<<ans[qi][qj]<<" ";
}
cout<<endl;
}
return 0;
}