106

yoakashi

jwh
csuperj

mhmh

djw

13小时前
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 100010;
int a[N],temp[N];

LL merge_sort(int l,int r)
{
if(l >= r) return 0;
int mid = l + r >> 1;
//递归调用分别求左右两边的逆序对数量
LL res = merge_sort(l,mid) + merge_sort(mid+1,r);

int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r)
{
if(a[i] <= a[j]) temp[k++] = a[i++];
else
{
res += mid - i + 1;
temp[k++] = a[j++];
}
}

while(i <= mid) temp[k++] = a[i++];
while(j <= r) temp[k++] = a[j++];

for(int i=l,k=0; i<=r; i++,k++)
{
a[i] = temp[k];
}
return res;
}

int main()
{
int n;
cin >> n;
for(int i=0; i<n; i++) scanf("%d",&a[i]);
//归并排序求跨过mid的逆序对数量
cout << merge_sort(0,n-1) <<endl;
return 0;
}


16小时前

# 思路

::::::::::::::::::::::::::::::::::

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

const int N = 100010;
pair<int,int> order[N];

int st[N],score[N],last[N];
int n,m,T;

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

sort(order,order+m);

for(int i=0; i<m;)
{
int j = i;
while(j < m && order[i] == order[j]) j++;
int t = order[i].first, id = order[i].second, cnt = j - i;
i = j;

score[id] -= t - last[id] - 1;
if(score[id] <= 3) st[id] = false;
if(score[id] < 0) score[id] = 0;

score[id] += cnt * 2;
if(score[id] > 5) st[id] = true;

last[id] = t;
}

for(int i=1; i<=n; i++)
{
if(last[i] < T)
{
score[i] -= T - last[i];
if(score[i] <= 3) st[i] = false;
}
}

int res = 0;
for(int i=1; i<=n; i++) res += st[i];
cout << res <<endl;
return 0;
}


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

const int N = 5010;
int s[N][N];

int main()
{
int n,r;
cin >> n >> r;
r = min(r,5001);

//让边界和r一样大，防止r的边界大于数据范围
int mx = r, ny = r;
for(int i=0; i<n; i++)
{
int x,y,w;
scanf("%d %d %d",&x,&y,&w);
x++,y++;
s[x][y] += w;
mx = max(mx,x);
ny = max(ny,y);
}

for(int i=1; i<=mx; i++)
for(int j=1; j<=ny; j++)
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + s[i][j];

int res = 0;
for(int i=r; i<=mx; i++)
for(int j=r; j<=ny; j++)
res = max(s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r], res);

cout << res << endl;
return 0;
}


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

const int N = 100010;
long long a[N],s[N],cnt[N];

int main()
{
int n,k;
cin >> n >> k;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
s[i] = s[i-1] + a[i];
}

long long res = 0;
cnt[0]++;
for(int i=1; i<=n; i++)
{
res += cnt[s[i] % k];
cnt[s[i] % k] ++;
}

cout << res <<endl;
return 0;
}


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

const int N = 1010;
int a[N][N],s[N][N];

int main()
{
int n,m,q;
cin >> n >> m >> q;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
scanf("%d",&a[i][j]);

//创建前缀和
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + a[i][j];

for(int i=0; i<q; i++)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << endl;
}
return 0;
}


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

const int N = 100010;
int a[N],s[N];

int main()
{
int n,m;
cin >> n >> m;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
s[i] = s[i-1] + a[i];
}

for(int i=0; i<m; i++)
{
int l,r;
cin >> l >> r;
cout << s[r] - s[l-1] << endl;
}
return 0;
}


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

typedef long long LL;
const int N = 100010;
int a[N],s[N];

int main()
{
int n;
cin >> n;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
s[i] = s[i-1] + a[i];
}

if(s[n] % 3) puts("0");
else
{
LL cnt = 0, res = 0;
for(int i=3; i<=n; i++)
{
if(s[i-2] == s[n] / 3) cnt++;
if(s[n] - s[i-1] == s[n] / 3) res += cnt;
}
cout << res;
}
return 0;
}


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

int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool checkvalid(int year,int month,int day)
{
if(!month || month > 12) return false;
if(day == 0) return false;
if(month != 2)
{
if(day > days[month])
return false;
}
else
{
int leap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
if(day > 28 + leap) return false;
}
return true;
}

void printdate(int date)
{
printf("%04d-%02d-%02d\n",date / 10000,date % 10000 / 100,date % 100);
}

int main()
{
//读入日期
int a,b,c;
scanf("%d/%d/%d",&a,&b,&c);

for(int i=19600101; i<=20591231; i++)
{
int year = i / 10000;
int month = i % 10000 / 100;
int day = i % 100;
if(checkvalid(year,month,day))
{
if((year % 100 == a && month == b && day == c) //年月日
||(month == a && day == b && year % 100 == c) //月日年
|| (day == a && month == b && year % 100 == c)) //日月年
printdate(i);
}
}

return 0;
}


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
int w,m,n;
cin >> w >> m >> n;

m--,n--;
int x1 = m / w, x2 = n / w;
int y1 = m % w, y2 = n % w;
if(x1 % 2) y1 = w - 1 - y1;
if(x2 % 2) y2 = w - 1 - y2;

cout << abs(x1-x2) + abs(y1-y2) << endl;
return 0;
}


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

const int N = 100010;

void merge_sort(int *q,int left,int right,int *temp)
{
if(left>=right) return;

int mid = left + right >> 1;
merge_sort(q,left,mid,temp),merge_sort(q,mid+1,right,temp);

int index = 0, i = left, j = mid + 1;
while(i <= mid && j <= right)
{
if(q[i] <= q[j]) temp[index++] = q[i++];
else temp[index++] = q[j++];
}
while(i <= mid) temp[index++] = q[i++];
while(j <= right) temp[index++] = q[j++];
for(int i=left,j=0; i<=right; i++,j++) q[i] = temp[j];

}

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

int *temp = (int *)malloc(sizeof(int)*n);
merge_sort(q,0,n-1,temp);

for(int i=0; i<n; i++) printf("%d ",q[i]);
return 0;
}