Submission #402768

#	Time	Username	Problem	Language	Result	Execution time	Memory
402768		leductoan	Lasers (NOI19_lasers)	C++14	100 / 100	445 ms	69268 KiB

lasers

/** try <3 **/
#include<bits/stdc++.h>

using namespace std;

#define task "sol"
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define zs(v) ((int)(v).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define CNTBIT __builtin_popcountll
#define ALL(v) (v).begin(),(v).end()
#define endl '\n'

typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;

const int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
const int dxx[8]={-1, -1, 0, 1, 1, 1, 0, -1}, dyy[8]={0, 1, 1, 1, 0, -1, -1, -1};
const ll mod=1000000007; /// 998244353
const int base=311;
const int N=5e5+5;

int n,m;
vector<int> a[N];

void gogo()
{
    cin>>m>>n;
    for(int i=1;i<=n;++i)
    {
        int x;
        cin>>x;
        for(int j=1;j<=x;++j)
        {
            int k;
            cin>>k;
            a[i].pb(k);
        }
    }

    vector<pii> all;

    for(int i=1;i<=n;++i)
    {
        vector<pii> seg;

        int sum=0;
        for(int j:a[i]) sum+=j;

        seg.pb(mp(1,m-sum));
        seg.pb(mp(sum+1,m));

        int s=0;
        for(int j:a[i])
        {
            s+=j;
            seg.pb(mp(s+1,m-(sum-s)));
        }

        sort(ALL(seg));

//        for(pii j:seg) cout<<j.fi<<' '<<j.se<<endl;
//        cout<<endl;

        int L=-1, R=-1;
        for(pii i:seg)
        {
            if(L<=i.fi&&i.fi<=R)
            {
                R=max(R,i.se);
            }
            else if(i.fi>R)
            {
                if(L!=-1)
                {
                    all.pb(mp(L,R));
                }
                L=i.fi;
                R=i.se;
            }
        }
        all.pb(mp(L,R));
    }

    vector<int> s;

    for(pii i:all)
    {
        s.pb(i.fi);
        s.pb(i.se);
//        cout<<i.fi<<' '<<i.se<<endl;
    }

    sort(ALL(s));
    s.resize(unique(ALL(s))-s.begin());

    int mx=0;
    for(pii &i:all)
    {
        i.fi=lb(ALL(s),i.fi)-s.begin();
        i.se=lb(ALL(s),i.se)-s.begin();
        i.fi*=2;
        i.se*=2;
        mx=max(mx,i.se);
    }

    vector<int> f(mx+5,0);
    int ans=0;

    for(pii i:all)
    {
        f[i.fi]++;
        f[i.se+1]--;
    }
    for(int i=1;i<=mx;++i) f[i]+=f[i-1];
    for(int i=0;i<=mx;++i)
    {
        if(f[i]<n) continue;
        int j=i;
        while(j<mx&&f[j+1]==f[i]) ++j;
//        cout<<s[i/2]<<' '<<s[j/2]<<endl;

        assert(j%2==0&&i%2==0);
        ans+=s[j/2]-s[i/2]+1;
        i=j;
    }

    cout<<m-ans;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    gogo();
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lasers.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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