1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <stdio.h>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    long long int number;
    scanf("%lld\n", &number);


    bool isClosed = true;
    long long int currentVal;
    // now best closed interval
    long long int curBest = 0;

    map<long long int, long long int> intervals;
    long long int curStructState = 0;
    map<long long int, long long int>::iterator mapChecker, delBefore;
    long long int newMin = -1;
    long long int tmp;
    bool eras;


    for (int idx = 0; idx < number; ++idx) {
        scanf("%lld", &currentVal);
        if (currentVal == 0) {
            continue;
        }
        newMin = -1;
        // step 1 próba domknięcia i update isClosed
        mapChecker = intervals.lower_bound(-1*(curStructState + currentVal));
        if (mapChecker != intervals.end()) {
            tmp = -1;
            eras = false;
            while (mapChecker != intervals.end()) {
                if (tmp <= mapChecker->second) {
                    if (tmp > -1) {
                        eras = true;
                    }
                    delBefore = mapChecker;
                    tmp = mapChecker->second;
                }
                mapChecker ++;
            }
            if (eras == true){
                //cout << "eras\n";
                mapChecker = intervals.lower_bound(-1*(curStructState + currentVal));
                intervals.erase(mapChecker, delBefore);
            }



            newMin = idx - tmp;
            //cout<<mapChecker->first<<" map checker "<< mapChecker->second<< " " << idx  << " "<< newMin<< "\n";
        }
        // step 2 update mapy
        curStructState += currentVal;

        if (isClosed == true) {
            mapChecker = intervals.find(currentVal - curStructState);
            //cout << currentVal - curStructState << " map upd " <<  idx - curBest << " " <<  curStructState << "\n";
            if (mapChecker != intervals.end()) {
                mapChecker->second = max(mapChecker->second, idx - curBest);
            } else {
                intervals.insert(pair<long long int, long long int>(currentVal - curStructState, idx - curBest));
            }
        }

        // step 3 update isClosed i update curBest

        // todo update curBest/ isClosed
        if (newMin > 0) {
            //cout << "update curBest " << newMin << "\n";
            if (isClosed == true && currentVal > 0) {
                curBest = min(newMin, curBest);
            } else {
                curBest = newMin;
                isClosed = true;
            }

        } else {
            //cout << " prep closed" << idx << "\n";
            if (currentVal < 0) {
                isClosed = false;
            }
        }
    }

    if (isClosed == false) {
        printf("-1\n");
    } else {
        printf("%lld\n", curBest);
    }

//    for (mapChecker=intervals.begin(); mapChecker!=intervals.end(); ++mapChecker)
//        cout << mapChecker->first << " => " << mapChecker->second << '\n';
//
//    cout << curStructState;
    return 0;
}