結果

問題 No.284 門松と魔法(2)
ユーザー potetisensei
提出日時 2015-11-17 02:26:06
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,281 bytes
コンパイル時間 519 ms
コンパイル使用メモリ 50,560 KB
実行使用メモリ 7,880 KB
最終ジャッジ日時 2024-09-13 15:45:23
合計ジャッジ時間 2,547 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 WA * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:20:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   20 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:23:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   23 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <vector>
#include <set>
using namespace std;

#define PLUS 1
#define MINUS 0

typedef pair<int, int> Interval;
typedef pair<int, Interval> Pair;

int l, r;
int n;
int sub;
bool dir;
vector<int> as;
set<Pair> intervals;

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        int a;
        scanf("%d", &a);
        if (i == 0 || as.back() != a) as.push_back(a);
        else sub++;
    }

    n -= sub;
    sub = 0;
    if (n <= 2) {
        puts("0");
        return 0;
    }

    l = 0;
    r = 1;
    dir = as[0] < as[1];
    for (int i=1; i<n-1; i++) {
        if (dir == as[i] < as[i+1]) r++;
        else {
            intervals.insert(Pair(r-l+1, Interval(l, r)));
            l = r;
            r = l+1;
            dir ^= 1;
        }
    }
    intervals.insert(Pair(r-l+1, Interval(l, r)));

    while (!intervals.empty()) {
        int num = intervals.rbegin()->first;
        int l = intervals.rbegin()->second.first;
        int r = intervals.rbegin()->second.second;
        if (num <= 2) break;
        intervals.erase(Pair(num, Interval(l, r)));
        sub += num-2;
        intervals.insert(Pair(2, Interval(l, r)));
    }

    if (n - sub <= 2) {
        puts("0");
    } else {
        printf("%d\n", n-sub);
    }
}
0