//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;
typedef struct _node{
lli val,nl,nr,nroot;
struct _node *left,*right;
}node;
const lli INF = 0xFFFFFFFFFFFFFFFL;
const lli mod = 1000000007L;
lli T,n,i,m,j,k,in,cnt,l,sz;
vi a,b,zz;
set<lli> s;
vi :: iterator it;
node *root;
//priority_queue < lli , vector < lli > , cmp > pq;// min priority_queue .
node *makeNode(lli n)
{
node *nd= (node *) malloc(sizeof(node));
nd->val=n;
nd->left=nd->right=NULL;
nd->nl=nd->nr=nd->nroot=0;
return nd;
}
node* bst(lli l,lli r)
{
if(l==r)
return makeNode(b[l]);
if(l>r)
return NULL;
lli m=l+(r-l)/2;
node* nd=makeNode(b[m]);
nd->left=bst(l,m-1);
nd->right=bst(m+1,r);
return nd;
}
void insert(lli n)
{
//cout<<endl<<"insert "<<n<<endl;
node *nd=root;
while(nd->val!=n)
{
if(nd->val>n)
{
// cout<<"add "<<nd->val<<" left"<<endl;
nd->nl++;
nd=nd->left;
}
else
{
// cout<<"add "<<nd->val<<" right"<<endl;
nd->nr++;
nd=nd->right;
}
}
nd->nroot++;
// cout<<"add "<<nd->val<<" nroot"<<endl<<endl;
}
void del(lli n)
{
node *nd=root;
while(nd->val!=n)
{
if(nd->val>n)
{
nd->nl--;
nd=nd->left;
}
else
{
nd->nr--;
nd=nd->right;
}
}
nd->nroot--;
}
lli query(lli n)
{
node *nd=root;
lli cnt=0;
while(nd->val!=n)
{
if(nd->val>n)
{
nd=nd->left;
}
else
{
cnt+=nd->nl+nd->nroot;
nd=nd->right;
}
}
cnt+=nd->nl;
return cnt;
}
void preorder(node *nd)
{
if(nd==NULL)
return;
preorder(nd->left);
cout<<nd->val<<" ";
preorder(nd->right);
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
scanf(" %lld",&n);
fo(i,n)
{
scanf(" %lld",&in);
zz.pb(in);
}
scanf(" %lld",&k);
a.clear();a.reserve(n+4);
lli sum=0;
a.pb(0);
s.insert(0);
fo(i,n)
{
in=zz[i];
sum+=in-k;
a.pb(sum);
s.insert(sum);
}
//for(auto &x:a)
// cout<<x<<" ";
//cout<<endl;
for(auto &x:s)
{
sz++;
b.pb(x);
}
root = bst(0,sz-1);
//cout<<root->val;
//preorder(root);
//cout<<endl;
//return 0;
for(i=0;i<=n;++i)
{
insert(a[i]);
}
lli cnt=0;
for(i=0;i<n;++i)
{
del(a[i]);
cnt+=query(a[i]);
//cout<<a[i]<<" "<<query(a[i])<<endl;
}
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:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %lld",&n);
~~~~~^~~~~~~~~~~~
vudu.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %lld",&in);
~~~~~^~~~~~~~~~~~~
vudu.cpp:164: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 |
8 ms |
1272 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1272 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1272 KB |
Output is correct |
| 4 |
Execution timed out |
1076 ms |
66560 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1022 ms |
66560 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1037 ms |
66560 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1020 ms |
66560 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1047 ms |
66560 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1029 ms |
66560 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1038 ms |
66560 KB |
Time limit exceeded |
