제출 #413664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413664		blue	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1077 ms	55200 KiB

sumzero

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

struct loc
{
    long long sm;
    int i;
};

bool operator < (loc A, loc B)
{
    if(A.sm == B.sm) return A.i < B.i;
    return A.sm < B.sm;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    int N;
    cin >> N;

    vector<int> nxt[N+2];

    multiset<loc> L;

    long long c[N+2];
    c[0] = 0;
    L.insert(loc{0, 0});

    for(int i = 1; i <= N; i++)
    {
        cin >> c[i];
        c[i] += c[i-1];

        L.insert(loc{c[i], i});
    }

    while(!L.empty())
    {
        vector<int> p;
        long long s = L.begin()->sm;

        while(!L.empty() && L.begin()->sm == s)
        {
            p.push_back(L.begin()->i);
            L.erase(L.begin());
        }

        for(int i = 0; i+1 < p.size(); i++)
        {
            nxt[ p[i] + 1 ].push_back(p[i+1]);
        }
    }
    // cerr << "check\n";
    for(int i = N; i >= 1; i--)
    {
        if(nxt[i+1].size() == 0) continue;

        if(nxt[i].empty())
        {
            nxt[i].push_back(nxt[i+1][0]);
        }
        else
        {
            nxt[i][0] = min(nxt[i][0], nxt[i+1][0]);
        }
    }


    // cerr << "c\n";

    for(int j = 1; j <= 20; j++)
    {
        // cerr << j << '\n';
        for(int i = 1; i <= N; i++)
        {
            if(nxt[i].size() <= j-1) continue;
            if(nxt[i][j-1] + 1 > N) continue;
            if(nxt[ nxt[i][j-1] + 1 ].size() <= j-1) continue;
            nxt[i].push_back(nxt[ nxt[i][j-1] + 1 ][j-1]);
        }
    }

        // cerr << "chec2\n";
    int Q;
    cin >> Q;

    for(int q = 1; q <= Q; q++)
    {
        int L, R;
        cin >> L >> R;

        int res = 0;
        for(int j = 20; j >= 0; j--)
        {
            if(j >= nxt[L].size()) continue;
            if(nxt[L][j] > R) continue;
            L = nxt[L][j] + 1;
            // cerr << (1 << j) << ' ' << L << '\n';
            res += (1 << j);
        }
        cout << res << '\n';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp: In function 'int main()':
sumzero.cpp:55:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i = 0; i+1 < p.size(); i++)
      |                        ~~~~^~~~~~~~~~
sumzero.cpp:83:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |             if(nxt[i].size() <= j-1) continue;
      |                ~~~~~~~~~~~~~~^~~~~~
sumzero.cpp:85:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |             if(nxt[ nxt[i][j-1] + 1 ].size() <= j-1) continue;
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
sumzero.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |             if(j >= nxt[L].size()) continue;
      |                ~~^~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39