답안 #77500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
77500 2018-09-28T09:04:47 Z aryanc403 Vudu (COCI15_vudu) C++17
140 / 140
758 ms 32424 KB
//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