Godlessness

1619

class MinStack {
public:
/** initialize your data structure here. */
//建立两个栈，一个记录数值，一个记录最小值
stack<int> value;
stack<int> MIN;
MinStack() {

}

void push(int x) {
value.push(x);
if(MIN.empty()||x<=MIN.top())
{
MIN.push(x);
}
}

void pop() {
if(value.top()==MIN.top())
{
MIN.pop();
}
value.pop();
}

int top() {
return value.top();
}

int getMin() {
return MIN.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/


#include<iostream>
#include<algorithm>
using namespace std;

const int N=110;
int a[N][N];
int sum[N][N];
int res=-1e9;
int n;

int main()
{
cin>>n;

for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}

//枚举边界
for(int i=1;i<=n;i++)//上边界
for(int j=i;j<=n;j++)//下边界
{
int temp=0;

for(int k=1;k<=n;k++)
{
temp+=sum[j][k]-sum[j][k-1]-sum[i-1][k]+sum[i-1][k-1];

res=max(temp,res);
if(temp<0) temp=0;

}
}

cout<<res<<endl;

return 0;
}


#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL,LL> PII;
const int N=5e4+10;
PII cows[N];
int n;
LL wcow[N];

int main()
{
cin>>n;

for(int i=0;i<n;i++)
{
LL w,s;
scanf("%lld%lld",&w,&s);
cows[i].first=w+s;
cows[i].second=s;
}

sort(cows,cows+n);

LL sum=0,mindan=-1e9;
for(int i=0;i<n;i++)
{
wcow[i]=cows[i].first-cows[i].second;
sum+=wcow[i];
mindan=max(mindan,sum-wcow[i]-cows[i].second);
}

cout<<mindan<<endl;

return 0;
}


#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int g[5][5];

void operation()
{
int ans,time=1e9,k;

for(k=0;k<1<<16;k++)
{
int res=0;
int back[5][5];
memcpy(back,g,sizeof g);

for(int i=0;i<16;i++)
{
if(k>>i&1)
{
res++;
int x,y;

if(i==0||i==4||i==8||i==12) y=1;
else if(i==1||i==5||i==9||i==13) y=2;
else if(i==2||i==6||i==10||i==14) y=3;
else y=4;
x=i/4+1;

for(int j=1;j<=4;j++) g[x][j]^=1;
for(int j=1;j<=4;j++)
{
if(j!=x)
g[j][y]^=1;
}
}
}

int p,q;
bool flag=true;
for(p=1;p<=4;p++)
for(q=1;q<=4;q++)
{
if(g[p][q]==1) flag=false;
}
if(flag==true)
{
if(time>res)
{
time=res;
ans=k;
}
}

memcpy(g,back,sizeof back);
}

cout<<time<<endl;
for(int i=0;i<16;i++)
{
if(ans>>i&1)
{
int x,y;

if(i==0||i==4||i==8||i==12) y=1;
else if(i==1||i==5||i==9||i==13) y=2;
else if(i==2||i==6||i==10||i==14) y=3;
else y=4;
x=i/4+1;

cout<<x<<" "<<y<<endl;
}
}
}

int main()
{
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
{
char t;
cin>>t;
if(t=='+') g[i][j]=1;
else g[i][j]=0;
}

operation();

return 0;
}


#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;

typedef pair<double,double> PDD;
const int N=1010;
int n,d;
PDD ioslate[N];

int main()
{
cin>>n>>d;
bool flag=true;

for(int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);

if(y>d)
{
flag=false;
break;
}

double D=sqrt(d*d-y*y);
ioslate[i].first=x-D;
ioslate[i].second=x+D;
}

sort(ioslate,ioslate+n);

if(flag==false)
{
cout<<-1;
return 0;
}

int cnt=0;
double pos=-1e9;
for(int i=0;i<n;i++)
{
if(pos<ioslate[i].first)
{
pos=ioslate[i].second;
cnt++;
}
else pos=min(pos,ioslate[i].second);//重点
}

cout<<cnt;
return 0;
}


#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
const int N=5e4+10;
pair<PII,int> cow[N];
int n;
int id[N];

int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
scanf("%d%d",&cow[i].first.first,&cow[i].first.second);
cow[i].second=i;
}

sort(cow,cow+n);

priority_queue<PII,vector<PII>,greater<PII>>heap;
for(int i=0;i<n;i++)
{
if(heap.empty()||heap.top().first>=cow[i].first.first)
{
PII stall;//记录每个区间的右端点
stall={cow[i].first.second,heap.size()+1};
id[cow[i].second]=stall.second;
heap.push(stall);
}
else
{
auto stall=heap.top();
heap.pop();
id[cow[i].second]=stall.second;
stall.first=cow[i].first.second;
heap.push(stall);
}
}

cout<<heap.size()<<endl;
for(int i=0;i<n;i++) printf("%d\n",id[i]);
return 0;
}


#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

typedef pair<int,int> PII;
const int N=2510;
int c,l;
PII spf[N];
int res;

int main()
{
map<int,int>cover;
cin>>c>>l;
for(int i=0;i<c;i++) cin>>spf[i].first>>spf[i].second;
for(int i=0;i<l;i++)
{
int a,b;
scanf("%d%d",&a,&b);
cover[a]+=b;
}

sort(spf,spf+c);

for(int i=c-1;i>=0;i--)
{
for(int j=spf[i].second;j>=spf[i].first;j--)
{
if(cover[j]>0)
{
cover[j]--;
res++;
break;
}
}
}

cout<<res;
return 0;
}


#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;

int main()
{
int p;
cin>>p;

while(p--)
{
//定义大根堆
//less表示按照从小到大顺序插入元素
priority_queue<int,vector<int>,less<int>>bigheap;
//定义小根堆
//greater表示按照从大到小顺序插入元素
priority_queue<int,vector<int>,greater<int>>smallheap;

int num,n,cnt=0;
scanf("%d%d",&num,&n);
printf("%d %d\n",num,(n+1)/2);

for(int i=1;i<=n;i++)
{
int number;
scanf("%d",&number);

if(bigheap.empty()||number<bigheap.top()) bigheap.push(number);
else smallheap.push(number);

if(bigheap.size()>smallheap.size()+1)
{
int t=bigheap.top();
bigheap.pop();
smallheap.push(t);
}

if(smallheap.size()>bigheap.size())
{
int t=smallheap.top();
bigheap.push(t);
smallheap.pop();
}

if(i&1)
{
cout<<bigheap.top();
cnt++;
if(cnt%10==0)cout<<endl;
else cout<<" ";
}
}
if(cnt%10!=0) printf("\n");
}

return 0;
}



//求逆序对数量
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

typedef long long LL;
const int N=5e5+10;
int q[N];
LL num;

LL merge_sort(int l,int r)//归并排序
{
if(l==r) return 0;

int mid=(l+r)/2;
num=merge_sort(l,mid)+merge_sort(mid+1,r);

int tmp[N];
int i=l,j=mid+1,cnt=0;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j]) tmp[cnt++]=q[i++];
else
{
tmp[cnt++]=q[j++];
num=num+mid-i+1;
}
}

while(i<=mid) tmp[cnt++]=q[i++];
while(j<=r) tmp[cnt++]=q[j++];

for(int i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];

return num;
}

int main()
{
int n;

while(scanf("%d",&n)&&n!=0)
{
num=0;//记录逆序对个数

for(int i=0;i<n;i++) scanf("%d",&q[i]);

cout<<merge_sort(0,n-1)<<endl;
}

return 0;
}


#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<map>
using namespace std;

const int N=2e5+10;
int lanuage[N];
map<int,int>num;//各个数没有大小之间的联系，所以可以用map存储
struct scients
{
int voice;
int word;
}mm[N];
int n,m;

int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&lanuage[i]);
num[lanuage[i]]++;
}
cin>>m;
for(int i=1;i<=m;i++) scanf("%d",&mm[i].voice);
for(int i=1;i<=m;i++) scanf("%d",&mm[i].word);

int choose=1;
int happya=0;
for(int i=1;i<=m;i++)//语音
{
if(num[mm[i].voice]>happya)
{
happya=num[mm[i].voice];
choose=i;
}
}

int happyb=0;
for(int i=1;i<=m;i++)//字幕
{
if(num[mm[i].voice]==happya)
{
if(num[mm[i].word]>happyb)
{
choose=i;
happyb=num[mm[i].word];
}
}
}

cout<<choose;
return 0;
}