liyx19

723

liyx19
1小时前
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=3e5+5;
int a[N],s[N];
typedef pair<int,int> PII;
vector<int> alls;
int find(int x){
int l=0,r=alls.size();
while(l<r){
int mid=(l+r)>>1;
if(alls[mid]>=x) r=mid;
else l=mid+1;
}
return r+1;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int x,c;
cin>>x>>c;
alls.push_back(x);
}
for(int i=1;i<=m;i++){
int l,r;
cin>>l>>r;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
int x=find(item.first);
a[x]+=item.second;
}
for(int i=1;i<=alls.size();i++){
s[i]=s[i-1]+a[i];
}
for(auto item : query){
int l=find(item.first),r=find(item.second);
cout<<s[r]-s[l-1]<<endl;
}
}


liyx19
1天前
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1005;
const double eps=1e-5;
struct AC{
double l,r;
}a[N];
int cmp(AC a,AC b){
if(a.r==b.r) return a.l<b.l;
return a.r<b.r;
}
int main(){
int n,d;
cin>>n>>d;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
if(y>d){
cout<<-1;
return 0;
}
a[i].l=(double)x-sqrt(d*d-y*y);
a[i].r=(double)x+sqrt(d*d-y*y);
}
sort(a+1,a+n+1,cmp);
double maxr=-1e9;
int ans=0;
for(int i=1;i<=n;i++){
if(a[i].l>maxr+eps) {
ans++;
maxr=a[i].r+eps;
}
}
cout<<ans<<endl;
}


liyx19
2天前
#include<iostream>
#define eps 1e-5
using namespace std;
const int N=100005;
int a[N];
int n,f;
bool check(double mid){
double s[N];
for(int i=1;i<=n;i++){
s[i]=a[i]-mid,s[i]+=s[i-1];
}
double val=1e9,ans=-1e9;
for(int i=f;i<=n;i++){
val=min(val,s[i-f]);
ans=max(ans,s[i]-val);
}
if(ans<=0) return false;
else return true;
}
int main(){
cin>>n>>f;
for(int i=1;i<=n;i++){
cin>>a[i];
}
double l=-1e6,r=1e6;
while(r-l>eps){
double mid=(l+r)/2;
if(check(mid)){
l=mid;
}
else r=mid;
}
cout<<(int)(r*1000);
}


liyx19
3天前
#include<iostream>
using namespace std;
int a[15][5];
int tub[15],sum[15];
int main(){
for(int i=1;i<=13;i++){
string sb;
getline(cin,sb);
int cnt=0;
sum[i]=4;
for(int j=0;j<sb.size();j++){
if(sb[j]>='A' && sb[j]<='Z'){
cnt++;
if(sb[j]=='A'){
a[i][cnt]=1;
}
if(sb[j]=='J'){
a[i][cnt]=11;
}
if(sb[j]=='Q'){
a[i][cnt]=12;
}
if(sb[j]=='K'){
a[i][cnt]=13;
}
}
if(sb[j]>='0' && sb[j]<='9'){
cnt++;
if(sb[j]=='0'){
a[i][cnt]=10;
}
else a[i][cnt]=sb[j]-'0';
}
}
}
int life=4;
while(life>0){
int x=a[13][5-life];
while(x!=13){
tub[x]++;
x=a[x][sum[x]--];
}
life--;
}
int ans=0;
for(int i=1;i<=12;i++){
if(tub[i]==4) ans++;
}
cout<<ans<<endl;
}


liyx19
3天前
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=50005;
struct AC{
int l,r,ver;
bool operator <(const AC &a)const
{
if(a.r==r) return l>a.l;
return r>a.r;
}
}a[N];
int cmp(AC a,AC b){
if(a.l==b.l) return a.r<b.r;
return a.l<b.l;
}
priority_queue<AC> q;
int m,ans[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
a[i].ver=i;
}
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
if(!q.empty() && q.top().r<a[i].l){
ans[a[i].ver]=ans[q.top().ver];
q.pop();
}
else{
m++;
ans[a[i].ver]=m;
}
q.push(a[i]);
}
cout<<m<<endl;
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
}


liyx19
3天前
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=2505;
struct Ac{
int l,r;
}a[N];
struct Wa{
int spf,cov;
}b[N];
int cmp(Wa a,Wa b){
return a.spf>b.spf;
}
int CMP(Ac a,Ac b){
return a.l>b.l;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
}
sort(a+1,a+n+1,CMP);
for(int i=1;i<=m;i++){
scanf("%d%d",&b[i].spf,&b[i].cov);
}
sort(b+1,b+m+1,cmp);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(b[j].cov>0&&b[j].spf>=a[i].l && b[j].spf<=a[i].r){
b[j].cov--;
ans++;
break;
}
}
}
cout<<ans<<endl;
}


liyx19
3天前
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct cmp
{
bool operator ()(int &a,int &b)
{
return a>b;
}
};
priority_queue<int,vector<int>,cmp> nu1,q1;
priority_queue<int> q2,nu2;
int main(){
int P;
cin>>P;
while(P--){
int ver,n,cnt=0;
cin>>ver>>n;
q1=nu1;
q2=nu2;
cout<<ver<<" "<<(n+1)/2<<endl;
for(int i=1;i<=n;i++){
int now;
cin>>now;
if(q1.empty()){
q1.push(now);
}
else if(now>q1.top())
{
q1.push(now);
}
else q2.push(now);
while(q1.size()<q2.size()){
q1.push(q2.top());
q2.pop();
}
while(q1.size()>q2.size()+1){
q2.push(q1.top());
q1.pop();
}
if(i&1){
cnt++;
cout<<q1.top()<<" ";
if(cnt%10==0) cout<<endl;
}
}
if(cnt%10!=0)puts("");
}
}


liyx19
4天前
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=310;
int s[N];
int f[N][N],n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++) s[i]+=s[i-1];
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int l=i,r=i+len-1;
f[l][r]=1e9;
for(int k=l;k<r;k++)
f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
}
cout<<f[1][n];
}


liyx19
4天前
#include<iostream>
#include<cstdio>
using namespace std;
const int N=105;
int a[N][N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int ans=-1e9;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int x=i;x<=n;x++){
for(int y=j;y<=n;y++){
ans=max(ans,a[x][y]-a[x][j-1]-a[i-1][y]+a[i-1][j-1]);
}
}
}
}
printf("%d",ans);
}


liyx19
5天前
#include<iostream>
#include<cstring>
using namespace std;
const int N=10,M=1e6+5;
char c[N][N];
int a[N][N],b[N][N];
struct AC{
int x,y;
}ans[M],res[M];
void turn(int x,int y){
for(int i=1;i<=4;i++){
b[i][y]^=1;
}
for(int j=1;j<=4;j++){
b[x][j]^=1;
}
b[x][y]^=1;
}
int main(){
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
cin>>c[i][j];
if(c[i][j]=='-') a[i][j]=1;
}
}
int n=1e9;
for(int i=1;i<(1<<17);i++){
bool ok=true;int ans1=0;
//memset(ans,0,sizeof ans);
for(int j=1;j<=4;j++){
for(int k=1;k<=4;k++) b[k][j]=a[k][j];
}
for(int j=1;j<=16;j++){
if(i>>(j-1)&1){
int dx=j/4+1,dy=j%4;
if(!dy){
dy=4;
dx--;
}
turn(dx,dy);
ans1++;
ans[ans1]={dx,dy};
/*if(ans1>n){
break;
ok=false;
}*/
}
}
for(int j=1;j<=4;j++){
for(int k=1;k<=4;k++){
if(!b[j][k]){
ok=false;
break;
}
}
}
if(ok){
cout<<ans1<<endl;
for(int j=1;j<=ans1;j++){
cout<<ans[j].x<<" "<<ans[j].y<<endl;
}
//ans1=n;
break;
}
}
/*cout<<n;
for(int i=1;i<=n;i++){
cout<<res[i].x<<" "<<res[i].y<<endl;
}*/
}