Submission #406409

#	Time	Username	Problem	Language	Result	Execution time	Memory
406409		Fidisk	Lasers (NOI19_lasers)	C++14	100 / 100	380 ms	41348 KiB

lasers

#include <bits/stdc++.h>
using namespace std;

#define oo 1e15
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=361;
const ll mod=998244353;
const ld eps=1e-5;
const ll maxn=1e9+9;

ll n,m,sum,pre,i,j,k,a[500009],cnt,sl[500009],last,res;
vector<pll> q;

void update(ll l,ll r,ll gt) {
    q.push_back({l,gt});
    q.push_back({r+1,-gt});
}

ll calc(ll l,ll r) {
    return r-l+1;
}

int main(){
    IO;
    last=1;
    cin>>m>>n;
    for (i=1;i<=n;i++) {
        cin>>k;
        sum=0;
        pre=0;
        for (j=1;j<=k;j++) {
            cin>>a[j];
            sum+=a[j];
        }
        update(1,m-sum,i);
        for (j=1;j<=k;j++) {
            pre+=a[j];
            sum-=a[j];
            update(pre+1,m-sum,i);
        }
    }
    sort(q.begin(),q.end());
    for (i=0;i<q.size();i++) {
        //cout<<q[i].fi<<' '<<q[i].se<<'\n';
        if (q[i].se>0) {
            if (sl[q[i].se]==0) {
                cnt++;
            }
            sl[q[i].se]++;
        }
        else {
            sl[-q[i].se]--;
            if (sl[-q[i].se]==0) {
                cnt--;
            }
        }
        if (i+1<q.size()&&q[i+1].fi!=q[i].fi) {
            if (cnt==n) {
                res+=calc(last,q[i+1].fi-1);
               // cout<<"! "<<last<<' '<<q[i+1].fi-1<<'\n';
            }
            last=q[i+1].fi;
        }
    }
    if (cnt==n) {
        res+=calc(last,m);
        //cout<<"! "<<last<<' '<<m<<'\n';
    }
    //cout<<res<<'\n';
    cout<<m-res<<'\n';
}

Compilation message (stderr)

lasers.cpp: In function 'int main()':
lasers.cpp:60:15: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (i=0;i<q.size();i++) {
      |              ~^~~~~~~~~
lasers.cpp:74:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         if (i+1<q.size()&&q[i+1].fi!=q[i].fi) {
      |             ~~~^~~~~~~~~

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