//Invitation to ICO Preparatory Contest #1
//ICOP1901
//mean array
/************************************************************************************************************************************************************************************
* *
* *
* **************** ************** * * **************** * * **************** * * **************** **************** *
* * * * * * * * * ** * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* **************** ************** ***************** **************** * * * * **************** * * **************** *
* * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * * ** * * * * * *
* * * * * * * * * * **************** * **************** **************** *
* *
* *
************************************************************************************************************************************************************************************/
#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")
#include<iostream>
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define fo(i,n) for(i=0;i<(n);++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define MAX 100002
#define PI 3.1415926535897932384626433832795
typedef long long int lli;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
const lli INF = 0xFFFFFFFFFFFFFFFL;
const lli mod = 1000000007L;
lli T,n,i,m,j,k,in,cnt,l,sz;
vi a,tmp;
vi :: iterator it;
void SORT(vi &a)
{
lli sz=(lli)a.size();
if(sz<=1)
return;
vi b,c;
b.clear();a.reserve(sz/2+2);
c.clear();a.reserve(sz/2+2);
lli i=0;
fo(i,sz/2)
b.pb(a[i]);
while(i<sz)
{
c.pb(a[i]);
i++;
}
SORT(b);
SORT(c);
b.pb(INF);
c.pb(INF);
lli j=0,k=0,l=0;
fo(i,sz)
{
if(b[j]<=c[k])
a[i]=b[j++];
else
{
while(l<sz/2&&c[k]>=b[l])
l++;
cnt+=sz/2-l;
a[i]=c[k++];
}
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
scanf(" %lld",&n);
a.clear();a.reserve(n+4);
lli sum=0;
a.pb(0);
cnt=0;
fo(i,n)
{
scanf(" %lld",&in);
tmp.pb(in);
}
scanf(" %lld",&k);
fo(i,n)
{
sum+=tmp[i]-k;
a.pb(sum);
}
SORT(a);
cnt=n*(n+1)/2-cnt;
printf("%lld",cnt);
return 0;
}
Compilation message
vudu.cpp:25:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable:4996)
vudu.cpp:26:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
vudu.cpp: In function 'int main()':
vudu.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %lld",&n);
~~~~~^~~~~~~~~~~~
vudu.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %lld",&in);
~~~~~^~~~~~~~~~~~~
vudu.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %lld",&k);
~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
9 ms |
632 KB |
Output is correct |
| 2 |
Correct |
5 ms |
672 KB |
Output is correct |
| 3 |
Correct |
5 ms |
756 KB |
Output is correct |
| 4 |
Correct |
725 ms |
31464 KB |
Output is correct |
| 5 |
Correct |
404 ms |
31464 KB |
Output is correct |
| 6 |
Correct |
634 ms |
31464 KB |
Output is correct |
| 7 |
Correct |
615 ms |
31464 KB |
Output is correct |
| 8 |
Correct |
557 ms |
31464 KB |
Output is correct |
| 9 |
Correct |
758 ms |
32424 KB |
Output is correct |
| 10 |
Correct |
621 ms |
32424 KB |
Output is correct |
