제출 #989789

#제출 시각아이디문제언어결과실행 시간메모리
989789PedroBigManSails (IOI07_sails)C++14
100 / 100
242 ms14156 KiB
#pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <list> #include <iomanip> #include <stdlib.h> #include <time.h> #include <cstring> using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef long double ld; #define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++) #define pb push_back #define mp make_pair #define pl pair<ll,ll> #define ff first #define ss second #define whole(x) x.begin(),x.end() #define DEBUG(i) cout<<"Pedro "<<i<<endl #define INF 1000000000000000000LL #define EPS ((ld)0.00000000001) #define pi ((ld)3.141592653589793) #define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);} ll mod=1000000007; template<class A=ll> void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;} template<class A=ll> void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} class ST { public: ll N; class SV //seg value { public: ll a; SV() {a=0LL;} SV(ll x) {a=x;} SV operator & (SV X) {SV ANS(a+X.a); return ANS;} }; class LV //lazy value { public: ll a; LV() {a=0LL;} LV(ll x) {a=x;} LV operator & (LV X) {LV ANS(a+X.a); return ANS;} }; SV upval(ll c) //how lazy values modify a seg value inside a node, c=current node { SV X(p[c].a+(range[c].ss-range[c].ff+1)*lazy[c].a); return X; } SV neuts; LV neutl; vector<SV> p; vector<LV> lazy; vector<pl> range; ST() {N=0LL;} ST(vector<ll> arr) { N = (ll) 1<<(ll) ceil(log2(arr.size())); REP(i,0,2*N) {range.pb(mp(0LL,0LL));} REP(i,0,N) {p.pb(neuts);} REP(i,0,arr.size()) {SV X(arr[i]); p.pb(X); range[i+N]=mp(i,i);} REP(i,arr.size(),N) {p.pb(neuts); range[i+N]=mp(i,i);} ll cur = N-1; while(cur>0) { p[cur]=p[2*cur]&p[2*cur+1]; range[cur]=mp(range[2*cur].ff,range[2*cur+1].ss); cur--; } REP(i,0,2*N) {lazy.pb(neutl);} } void prop(ll c) //how lazy values propagate { p[c] = upval(c); lazy[2*c]=lazy[c]&lazy[2*c]; lazy[2*c+1]=lazy[c]&lazy[2*c+1]; lazy[c]=neutl; } SV query(ll a,ll b, ll c=1LL) //range [a,b], current node. initially: query(a,b) { if(a>b) {return neuts;} ll x=range[c].ff; ll y=range[c].ss; if(y<a || x>b) {return neuts;} if(x>=a && y<=b) {return upval(c);} prop(c); SV ans = query(a,b,2*c)&query(a,b,2*c+1); return ans; } void update(LV s, ll a, ll b, ll c=1LL) //update LV, range [a,b], current node, current range. initially: update(s,a,b) { if(a>b) {return;} ll x=range[c].ff; ll y=range[c].ss; if(y<a || x>b) {return ;} if(x>=a && y<=b) { lazy[c]=s&lazy[c]; return; } prop(c); update(s,a,b,2*c); update(s,a,b,2*c+1); p[c]=upval(2*c)&upval(2*c+1); } }; ST S; set<ll> borders; ll N, H; void check(ll x) { if(x==0 || x>=H) {return;} borders.erase(x); ll val_left = S.query(x-1,x-1).a; ll val = S.query(x,x).a; if(val_left!=val) {borders.insert(x);} } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(20); cin>>N; vector<pl> p; pl cur; H=0LL; REP(i,0,N) {cin>>cur.ff>>cur.ss; H=max(H,cur.ff); cur.ff--; p.pb(cur);} vector<ll> xx(H,0LL); S = ST(xx); sort(whole(p)); borders.insert(0LL); ll thisH, K, L; set<ll>::iterator it; ll start, finish; REP(i,0,N) { thisH = p[i].ff; K = p[i].ss; L = thisH-K+1LL; it = borders.upper_bound(L); it--; start = *it; it++; if(it==borders.end()) {finish = thisH;} else {finish = min(*it -1LL,thisH);} S.update(1LL,finish+1,thisH); K-=(thisH-finish); S.update(1LL,start,start+K-1); check(start); check(start+K); check(finish+1); check(thisH+1); } ll ans = 0LL; REP(i,0,H) { K = S.query(i,i).a; ans+=((K*(K-1LL))/2LL); } cout<<ans<<endl; return 0; }

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

sails.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization ("O3")
      | 
sails.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      |
#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...