Submission #248679

#	Time	Username	Problem	Language	Result	Execution time	Memory
248679		SamAnd	Lasers (NOI19_lasers)	C++17	100 / 100	216 ms	18268 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 500005;

int n, d;

int a[N];

int p[N], s[N];

void solv()
{
    scanf("%d%d", &d, &n);
    vector<pair<int, int> > v;
    while (n--)
    {
        int m;
        scanf("%d", &m);
        for (int i = 1; i <= m; ++i)
            scanf("%d", &a[i]);

        for (int i = 1; i <= m; ++i)
            p[i] = p[i - 1] + a[i];
        s[m + 1] = 0;
        for (int i = m; i >= 1; --i)
            s[i] = s[i + 1] + a[i];
        int x = 1;
        for (int i = 0; i <= m; ++i)
        {
            int l = 1 + p[i];
            int r = d - s[i + 1];
            if (l > r)
                continue;
            if (x < l)
            {
                v.push_back(m_p(x, l - 1));
            }
            x = max(x, r + 1);
        }
        if (x <= d)
            v.push_back(m_p(x, d));
    }
    vector<pair<int, int> > u;
    for (int i = 0; i < v.size(); ++i)
    {
        u.push_back(m_p(v[i].fi, 1));
        u.push_back(m_p(v[i].se + 1, -1));
    }
    sort(all(u));
    int p = 0;
    int ans = 0;
    for (int i = 0; i < u.size(); ++i)
    {
        p += u[i].se;
        if (p > 0)
            ans += (u[i + 1].fi - u[i].fi);
    }
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

lasers.cpp: In function 'void solv()':
lasers.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
lasers.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < u.size(); ++i)
                     ~~^~~~~~~~~~
lasers.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &d, &n);
     ~~~~~^~~~~~~~~~~~~~~~
lasers.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &m);
         ~~~~~^~~~~~~~~~
lasers.cpp:28:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i]);
             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13