Submission #1092361

#TimeUsernameProblemLanguageResultExecution timeMemory
1092361MrPavlitoSails (IOI07_sails)C++17
0 / 100
1065 ms14372 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define sc second //#define endl "\n" #define pii pair<int,int> using namespace std; const int MAXN = 1e5+5; const int mod7 = 1e9+7; const long long inf = 1e18; vector<int> visine(MAXN); vector<pii> seg(MAXN<<2, {-1,-1}); vector<int> lazy(MAXN<<2, 0); int rez; int p; void push(int nod, int tl, int tr) { if(lazy[nod] == 0)return; if(tl != tr) { lazy[nod<<1] += lazy[nod]; lazy[nod<<1|1] += lazy[nod]; } seg[nod].fi += lazy[nod]; seg[nod].sc += lazy[nod]; lazy[nod] = 0; } int query(int nod, int tl, int tr, int l, int r) { push(nod,tl,tr); if(tl> r || tr<l || tl>tr)return inf; if(tl>=l && tr<=r)return seg[nod].fi; int mid = tl+tr>>1; return min(query(nod<<1, tl, mid, l, r) ,query(nod<<1|1, mid+1,tr, l,r)); } void update(int nod, int tl, int tr, int l, int r, int&nm) { push(nod, tl, tr); //if(seg[nod].fi > p)return; if(nm <=0)return; if(tl > r)return; if(tr - tl+1 <= nm && seg[nod].fi == seg[nod].sc) { nm-= (tr-tl+1); lazy[nod]++; push(nod, tl, tr); return; } if(tl==tr)return; int mid = tl+tr>>1; push(nod<<1, tl, mid); push(nod<<1|1, mid+1, tr); if(seg[nod<<1|1] <= seg[nod<<1]) { update(nod<<1|1, mid+1, tr,l,r,nm); update(nod<<1, tl, mid,l,r,nm); } else { update(nod<<1, tl, mid,l,r,nm); update(nod<<1|1, mid+1, tr,l,r,nm); } seg[nod].fi = min(seg[nod<<1].fi,seg[nod<<1|1].fi); seg[nod].sc = max(seg[nod<<1].sc,seg[nod<<1|1].sc); } void get(int nod, int tl, int tr, int index) { push(nod, tl, tr); rez = max(rez, seg[nod].fi); //cout << rez << endl; if(tl == tr)return; int mid = tl+tr>>1; if(index <=mid)get(nod<<1, tl, mid, index); else get(nod<<1|1, mid+1, tr, index); } signed main() { ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0); int tt=1; //cin >> tt; while(tt--) { int n; cin >> n; vector<pii> niz(n); int mx = 0; for(int i=0; i<n; i++) { cin >> niz[i].fi >> niz[i].sc; mx = max(mx, niz[i].fi); } sort(all(niz)); for(int i=0; i<n; i++)cout << niz[i].fi << " " << niz[i].sc << endl; for(int i=0; i<n; i++) { int tr = niz[i].sc; p = query(1, 1,mx, 1, niz[i].fi); int preveal = p; update(1,1,mx,1,niz[i].fi,tr); //p++; if(tr>0)update(1,1,mx,1,niz[i].fi,tr); } int finalrez = 0; for(int j=1; j<=mx; j++) { rez = -1; get(1,1,mx,j); finalrez+= (rez)*(rez+1)/2; } cout << finalrez << endl; } }

Compilation message (stderr)

sails.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
sails.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int mid = tl+tr>>1;
      |               ~~^~~
sails.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int&)':
sails.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = tl+tr>>1;
      |               ~~^~~
sails.cpp: In function 'void get(long long int, long long int, long long int, long long int)':
sails.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = tl+tr>>1;
      |               ~~^~~
sails.cpp: In function 'int main()':
sails.cpp:109:17: warning: unused variable 'preveal' [-Wunused-variable]
  109 |             int preveal = p;
      |                 ^~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...