oj.uz

답안 #92837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92837 2019-01-05T09:39:34 Z SamAnd Money (IZhO17_money) C++17
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;

int n;
int a[N];

int t[N];

void ubd(int x)
{
    while (x < N)
    {
        t[x]++;
        x += (x & (-x));
    }
}

int qry(int l, int r)
{
    if (l > r)
        return 0;
    int ans = 0;
    while (r > 0)
    {
        ans += t[r];
        r -= (r & (-r));
    }
    --l;
    while (l > 0)
    {
        ans -= t[l];
        l -= (l & (-l));
    }
    return ans;
}

int main()
{
    //freopen("input2.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int ans = 1;
    ubd(a[1]);
    int s = a[1], ss, ssq;
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] >= a[i - 1] && qry(a[i - 1] + 1, a[i] - 1) == 0)
        {
            if (a[i] == s)
                continue;
            else if (a[i - 1] == s)
            {
                ss = a[i];
                ssq = 1;
            }
            else
            {
                if (a[i] == ss)
                {
                    ssq++;
                }
                else if (a[i - 1] == ss)
                {
                    if (qry(a[i - 1], a[i - 1]) == ssq)
                        continue;
                    else
                    {
                        ++ans;
                        s = a[i];
                    }
                }
                else
                {
                    if (qry(a[i - 1], a[i - 1]))
                    {
                        ++ans;
                        s = a[i];
                    }
                }
            }
        }
        else
        {
            ++ans;
            s = a[i];
        }
        ubd(a[i]);
    }
    cout << ans << endl;
    return 0;
}

Compilation message

money.cpp: In function 'int main()':
money.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
money.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
money.cpp:66:21: warning: 'ssq' may be used uninitialized in this function [-Wmaybe-uninitialized]
                     if (qry(a[i - 1], a[i - 1]) == ssq)
                     ^~
money.cpp:46:19: warning: 'ss' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int s = a[1], ss, ssq;
                   ^~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -