Submission #976487

#TimeUsernameProblemLanguageResultExecution timeMemory
976487MuhammadSaramMeteors (POI11_met)C++17
74 / 100
1666 ms65536 KiB
/********************* بسم الله الرحمن الرحيم ***********************/ /******************** ٱلْحَمْدُ لِلَّٰهِ رَبِّ ٱلْعَالَمِينَ *************************/ /******************* Prophet Muhammad صلى الله عليه وسلم ************/ /*********************** وَقُل رَّبِّ زِدْنِي عِلْمًا **************************/ #ifdef ONLINE_JUDGE #pragma GCC optimize("Ofast") #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #else #endif #include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define in binary_search #define ll long long #define ld long double #define Hey ios::sync_with_stdio(false); #define Welcome cin.tie(NULL), cout.tie(NULL); #define all(v) v.begin(),v.end() const int M = 3e5+1; int n,m,seg[4*M],lazy[4*M]; void push(int v,int s,int e) { int mid=(s+e)/2,lc=v*2,rc=lc+1; seg[lc]+=(mid-s)*lazy[v],seg[rc]+=(e-mid)*lazy[v]; lazy[lc]+=lazy[v],lazy[rc]+=lazy[v]; lazy[v]=0; } void modify(int l,int r,int x,int v=1,int s=0,int e=m) { if (l>=e or r<=s) return; if (l<=s and e<=r) { seg[v]+=x*(e-s); lazy[v]+=x; return; } int mid=(s+e)/2,lc=v*2,rc=lc+1; push(v,s,e); modify(l,r,x,lc,s,mid); modify(l,r,x,rc,mid,e); seg[v]=seg[lc]+seg[rc]; } int get(int l,int r,int v=1,int s=0,int e=m) { if (l>=e or r<=s) return 0; if (l<=s and e<=r) return seg[v]; push(v,s,e); int mid=(s+e)/2,lc=v*2,rc=lc+1; return get(l,r,lc,s,mid)+get(l,r,rc,mid,e); } void solve() { cin>>n>>m; vector<int> sps[n]; int exp[n]; for (int i=0;i<m;i++) { int x; cin>>x; sps[x-1].push_back(i); } for (int i=0;i<n;i++) cin>>exp[i]; int k,lg=22; cin>>k; vector<vector<int>> que; for (int i=0;i<k;i++) { int l,r,x; cin>>l>>r>>x; l--; que.push_back({l,r,x}); } vector<vector<int>> mid(k+1); int ps[n][2]; for (int i=0;i<n;i++) ps[i][0]=-1,ps[i][1]=1+k; for (int i=0;i<n;i++) mid[(ps[i][0]+ps[i][1])/2].push_back(i); while (lg--) { vector<vector<int>> mid1(k+1); for (int i=0;i<=k;i++) { for (int j:mid[i]) { int su=0; for (int a:sps[j]) su+=get(a,a+1); if (su>=exp[j]) ps[j][1]=i; else ps[j][0]=i; if (ps[j][1]-ps[j][0]>1) mid1[(ps[j][0]+ps[j][1])/2].push_back(j); } if (i<k and que[i][0]<que[i][1]) modify(que[i][0],que[i][1],que[i][2]); else if(i<k) { modify(que[i][0],m,que[i][2]); modify(0,que[i][1],que[i][2]); } } for (int i=0;i<M;i++) seg[i]=lazy[i]=0; mid=mid1; } for (int i=0;i<n;i++) { if (ps[i][1]==k+1) cout<<"NIE"<<endl; else cout<<ps[i][1]<<endl; } } signed main() { Hey! Welcome // S'up int t = 1; // cin >> t; cout<<fixed<<setprecision(20); while (t--) solve(); return 0; }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:136:5: warning: value computed is not used [-Wunused-value]
  136 |  Hey! Welcome // S'up
      |     ^
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...