제출 #412883

#제출 시각아이디문제언어결과실행 시간메모리
412883nicolaalexandraThe short shank; Redemption (BOI21_prison)C++14
10 / 100
1234 ms89160 KiB
#include <bits/stdc++.h> #define DIM 2000010 using namespace std; vector <int> L[DIM]; deque <int> d; int low[DIM],v[DIM],w[DIM],fth[DIM]; pair <int,int> intv[DIM]; int n,i,j,ans,D,t,k; struct segment_tree{ int maxi,poz,lazy; } aint[DIM*4]; struct event{ int val,idx,tip; }; vector <event> events; void build (int nod, int st, int dr){ if (st == dr){ aint[nod].poz = st; return; } int mid = (st+dr)>>1; build (nod<<1,st,mid); build ((nod<<1)|1,mid+1,dr); aint[nod].poz = aint[nod<<1].poz; } void update_lazy (int nod, int st, int dr){ if (!aint[nod].lazy) return; if (st != dr){ int fiu_st = nod<<1, fiu_dr = (nod<<1)|1; aint[fiu_st].maxi += aint[nod].lazy; aint[fiu_st].lazy += aint[nod].lazy; aint[fiu_dr].maxi += aint[nod].lazy; aint[fiu_dr].lazy += aint[nod].lazy; } aint[nod].lazy = 0; } void update (int nod, int st, int dr, int x, int y, int val){ update_lazy (nod,st,dr); if (x <= st && dr <= y){ aint[nod].maxi += val; aint[nod].lazy += val; update_lazy (nod,st,dr); return; } int mid = (st+dr)>>1; if (x <= mid) update (nod<<1,st,mid,x,y,val); if (y > mid) update ((nod<<1)|1,mid+1,dr,x,y,val); int fiu_st = nod<<1, fiu_dr = (nod<<1)|1; update_lazy (fiu_st,st,mid); update_lazy (fiu_dr,mid+1,dr); if (aint[fiu_st].maxi > aint[fiu_dr].maxi) aint[nod].maxi = aint[fiu_st].maxi, aint[nod].poz = aint[fiu_st].poz; else aint[nod].maxi = aint[fiu_dr].maxi, aint[nod].poz = aint[fiu_dr].poz; } inline int cmp (event a, event b){ if (a.val == b.val){ if (a.tip == b.tip && a.tip == 1) return intv[a.idx].second > intv[b.idx].second; return a.tip < b.tip; /// mai intai stergerile } return a.val < b.val; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>D>>t; for (i=1;i<=n;i++) cin>>v[i]; for (i=1;i<=n;i++){ while (!d.empty() && v[d.back()] + i - d.back() - t > 0) d.pop_back(); if (v[i] <= t){ low[i] = -1; ans++; } else { if (d.empty()) low[i] = -1; else { ans++; low[i] = d.back(); } } /// trb sa mai scot din stiva in caz ca o pozitie si ar pierde influenta pt ca /// vine alta care incepe un interval nou if (v[i] < t){ while (!d.empty() && v[d.back()] - d.back() >= v[i] - i) d.pop_back(); d.push_back(i); } } build (1,1,n); for (i=1;i<=n;i++) if (low[i] != -1 && low[i] <= i-1){ update (1,1,n,low[i],i-1,1); k++; intv[k] = make_pair(low[i],i-1); events.push_back({low[i],k,1}); events.push_back({i,k,0}); } sort (events.begin(),events.end(),cmp); d.clear(); int pos = 0; for (i=1;i<=n;i++){ while (pos < events.size() && events[pos].val == i && events[pos].tip == 0){ d.pop_back(); pos++; } while (pos < events.size() && events[pos].val == i && events[pos].tip == 1){ if (!d.empty()) fth[events[pos].idx] = d.back(); d.push_back(events[pos].idx); pos++; } if (!d.empty()) w[i] = d.back(); } for (;D--;){ int poz = aint[1].poz; ans -= aint[1].maxi; int x = w[poz]; while (x){ update (1,1,n,intv[x].first,intv[x].second,-1); x = fth[x]; } } cout<<ans; /* for (i=1;i<=n;i++) sort (L[i].begin(),L[i].end()); for (int pas=1;pas<=D;pas++){ int poz = aint[1].poz; ans -= aint[1].maxi; for (i=1;i<=poz;i++) while (L[i].size() && L[i].back() >= poz){ update (1,1,n,i,L[i].back(),-1); L[i].pop_back(); } } cout<<ans; */ return 0; }

컴파일 시 표준 에러 (stderr) 메시지

prison.cpp: In function 'int main()':
prison.cpp:142:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         while (pos < events.size() && events[pos].val == i && events[pos].tip == 0){
      |                ~~~~^~~~~~~~~~~~~~~
prison.cpp:147:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |         while (pos < events.size() && events[pos].val == i && events[pos].tip == 1){
      |                ~~~~^~~~~~~~~~~~~~~
#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...