Submission #643433

#TimeUsernameProblemLanguageResultExecution timeMemory
643433GaLzLasers (NOI19_lasers)C++14
100 / 100
461 ms58548 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; const ll mod=1e9+7; const ll maxn=5e5+5; const ll INF=1e18; #define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fi first #define se second #define pb push_back #define ub upper_bound #define lb lower_bound #define endl '\n' int l, r, x, u, sum[maxn], ls, st, cnt; vi row[maxn]; map<int, int> mp, ans; int main() { ok cin >> l >> r; for(int i=1; i<=r; i++) { cin >> x; for(int j=0; j<x; j++) { cin >> u; row[i].pb(u); sum[i]+=u; } } for(int i=1; i<=r; i++) { mp[l-sum[i]+1]++; mp[l+1]--; int lf=0, rg=l-sum[i]+1; x=row[i].size(); for(int j=0; j<x-1; j++) { lf+=row[i][j]; rg+=row[i][j]; mp[1]++; mp[lf+1]--; mp[rg]++; mp[l+1]--; } mp[1]++; mp[sum[i]+1]--; ls=0; st=0; for(auto it : mp) { it.se+=ls; ls=it.se; if(it.se==x+1 && !st) { st=it.fi; } else if(it.se!=x+1 && st) { ans[st]++; ans[it.fi]--; st=0; } } mp.clear(); } ls=0; st=0; for(auto it : ans) { it.se+=ls; ls=it.se; if(it.se>0 && !st) { st=it.fi; } else if(it.se<=0 && st) { cnt+=it.fi-st; st=0; } } cout << cnt; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...