Submission #295338

#	Time	Username	Problem	Language	Result	Execution time	Memory
295338		beso123	Lasers (NOI19_lasers)	C++14	100 / 100	761 ms	49120 KiB

lasers

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int L,n,pas,bal[1000005];
vector<int> g[1000005];
vector<pii> both(vector<pii> A,vector<pii> B){
    vector<pii> AB;
    AB.reserve(A.size()+B.size());
    AB.insert(AB.end(),A.begin(),A.end());
    AB.insert(AB.end(),B.begin(),B.end());
    return AB;
}
main(){
cin>>L>>n;
for(int k=1;k<=n;k++){
    int N;
    cin>>N;
    int sum=0;
    g[k].push_back(0);
    for(int i=1;i<=N;i++){
        int b;
        cin>>b;
        sum+=b;
        g[k].push_back(b);
    }
    bal[k]=L-sum;
}
vector<pii> v;
for(int k=1;k<=n;k++){
        int sum=0;
  int l=1,r=bal[k];
  vector<pii> bad,newv;
  for(int i=1;i<g[k].size();i++){
        int pos=g[k][i];
    sum+=g[k][i];
    int l1=sum+1,r1=sum+bal[k];
   if(l<=l1 && l1<=r)
    r=max(r1,r);
   else{
    bad.push_back({r+1,l1-1});
    l=l1;
    r=r1;
   }
  }
v=both(v,bad);
if(v.size()){
sort(v.begin(),v.end());
int cl=v[0].x,cr=v[0].y;
v.push_back({INT_MAX,INT_MAX});
for(int k=0;k<v.size();k++){
     if(cl<=v[k].x && v[k].x<=cr)
    cr=max(v[k].y,cr);
   else{
    newv.push_back({cl,cr});
    cl=v[k].x;
    cr=v[k].y;
   }
}
}
v.resize(0);
v=newv;
}
for(int k=0;k<v.size();k++){
        if(v[k].x<=v[k].y)
        pas+=(v[k].y-v[k].x+1);
}
cout<<pas;
return 0;
}

Compilation message (stderr)

lasers.cpp:16:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      |      ^
lasers.cpp: In function 'int main()':
lasers.cpp:36:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int i=1;i<g[k].size();i++){
      |               ~^~~~~~~~~~~~
lasers.cpp:37:13: warning: unused variable 'pos' [-Wunused-variable]
   37 |         int pos=g[k][i];
      |             ^~~
lasers.cpp:53:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 | for(int k=0;k<v.size();k++){
      |             ~^~~~~~~~~
lasers.cpp:66:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 | for(int k=0;k<v.size();k++){
      |             ~^~~~~~~~~

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