제출 #500737

#제출 시각아이디문제언어결과실행 시간메모리
500737innocentkittenSails (IOI07_sails)C++14
100 / 100
640 ms9344 KiB
#include <bits/stdc++.h> #define f first #define s second #define mp make_pair #define pb push_back #define p push #define ins insert #define t top #define fr front #define T1 10 #define T2 100 #define T3 1000 #define T4 10000 #define T5 100000 #define T6 1000000 #define H1 11 #define H2 105 #define H3 1010 #define H4 10010 #define H5 100010 #define H6 1000010 #define woof 31051 #define mod 998244353 #define MOD 1000000007 #define lnf 0 #define inf 1069999999 #define INF 2099999999 #define LNF 5e18 #define tc(T) template <class T> #define tcc(S, T) template <class S, class T> #define tccc(S, T, U) template <class S, class T, class U> using namespace std; mt19937 mr(time(0)); typedef long long int ll; typedef string str; typedef double dbl; struct LL { static ll m; // set to LNF for nomod long long int val; LL(ll v) {val=reduce(v);}; LL(int v) {val=reduce((ll)v);}; LL() {val=0;}; ~LL(){}; LL(const LL& l) {val=l.val;}; LL& operator=(int l) {val=l; return *this;} LL& operator=(ll l) {val=l; return *this;} LL& operator=(LL l) {val=l.val; return *this;} static void setMod(ll m) { assert(m); LL::m = m; } static long long int reduce(ll x, ll md = m) { x %= md; while (x >= md) x-=md; while (x < 0) x+=md; return x; } bool operator<(const LL& b) { return val<b.val; } bool operator<=(const LL& b) { return val<=b.val; } bool operator!=(const LL& b) { return val!=b.val; } bool operator==(const LL& b) { return val==b.val; } bool operator>=(const LL& b) { return val>=b.val; } bool operator>(const LL& b) { return val>b.val; } LL operator+(const LL& b) { return LL(val+b.val); } LL operator+(const ll& b) { return (*this+LL(b)); } LL& operator+=(const LL& b) { return (*this=*this+b); } LL& operator+=(const ll& b) { return (*this=*this+b); } LL operator-(const LL& b) { return LL(val-b.val); } LL operator-(const ll& b) { return (*this-LL(b)); } LL& operator-=(const LL& b) { return (*this=*this-b); } LL& operator-=(const ll& b) { return (*this=*this-b); } LL operator*(const LL& b) { return LL(val*b.val); } LL operator*(const ll& b) { return (*this*LL(b)); } LL& operator*=(const LL& b) { return (*this=*this*b); } LL& operator*=(const ll& b) { return (*this=*this*b); } static LL exp(const LL& x, const ll& y){ ll z = y; z = reduce(z,m-1); LL ret = 1; LL w = x; while (z) { if (z&1) ret *= w; z >>= 1; w *= w; } return ret; } LL& operator^=(ll y) { return (*this=LL(val^y)); } LL operator/(const LL& b) { return ((*this)*exp(b,-1)); } LL operator/(const ll& b) { return (*this/LL(b)); } LL operator/=(const LL& b) { return ((*this)*=exp(b,-1)); } LL& operator/=(const ll& b) { return (*this=*this/LL(b)); } }; ostream& operator<<(ostream& os, const LL& obj) { return os << obj.val; } ll LL::m = MOD; typedef pair<int,int> pii; typedef pair<int,ll> pil; typedef pair<int,LL> piL; typedef pair<ll,ll> pll; typedef pair<LL,LL> pLL; typedef pair<dbl,dbl> pdd; using namespace std; // sacrilege #define bts(a,x,b) ((a<x)&&(x<b)) #define btw(a,x,b) ((a<=x)&&(x<=b)) #define F0(x,n) for(ll x = 0; x < n; ++x) #define Fr(x,L,R) for(ll x = L; x < R; ++x) #define R0(x,n) for(ll x = n-1; x >= 0; --x) #define F1(x,n) for(ll x = 1; x <= n; ++x) #define FR(x,L,R) for(ll x = L; x <= R; ++x) #define R1(x,n) for(ll x = n; x >= 1; --x) #define RR(x,L,R) for(ll x = R; x >= L; --x) #define Rr(x,L,R) for(ll x = R-1; x >= L; --x) #define FE(x,ls) for(auto x : ls) #define FER(x,ls) for(auto &x : ls) #define srt(x) sort(x.begin(),x.end()) #define srtc(x,c) sort(x.begin(),x.end(),c) #define rev(x) reverse(x.begin(),x.end()) #define UB upper_bound #define LB lower_bound #define ub(x,v) upper_bound(x.begin(),x.end(),v) #define lb(x,v) lower_bound(x.begin(),x.end(),v) #define bs(x,v) binary_search(x.begin(),x.end(),v) #define dst(x,y) (ll)distance(x,y) #define nlt(x,v) (ll)dst(x.begin(),lb(x,v)) #define nle(x,v) (ll)dst(x.begin(),ub(x,v)) ll cases,N,M,Q,K,X,Y; //ifstream fin("exercise.in"); //ofstream fout("exercise.out"); ll rd() {ll x;cin>>x; return x;} dbl rdd() {dbl x;cin>>x; return x;} str rds() {str x;cin>>x; return x;} tc(T) void rds(char* S, T* sz) {*sz=strlen(strcpy(S,rds().c_str()));} tc(T) void rG(int sz, vector<vector<T>>& adj, int E = -18852946) { if (E == -18852946) E = sz-1; adj.clear(); F0(i,sz+1) adj.pb(vector<T>()); F0(i,E) { T a = rd(); T b = rd(); adj[a].pb(b); adj[b].pb(a); } } tcc(S,T) void rdv(vector<S>& vec, T* sz, bool flag = 1) { if (flag) *sz = rd(); F0(i,*sz) vec.pb(rd()); } void fl() {cout.flush();} void ds(int v) { cout << v << " "; } void ds(ll v) { cout << v << " "; } void ds(LL v) { cout << v << " "; } void ds(dbl v) { cout << v << " "; } void ds(char v) { cout << v << " "; } void ds(str v) { cout << v << " "; } void ds(char* v) { cout << v << " "; } tc(T) void ds(T* v, int t) { auto x = v; F0(i,t) ds(*(x++)); cout << endl; } tcc(S,T) void ds(pair<S,T> v) {cout << "( "; ds(v.f); cout << ", "; ds(v.s); cout << ") ";} tc(T) void ds(vector<T> v) { FE(x,v) ds(x); cout << endl; } tc(T) void panic(T out) { ds(out); exit(0); } tcc(S,T) bool updmin(S &a, T b) { S B = (S)b; if (B < a) {a = B; return 1;} return 0; } tcc(S,T) bool updmax(S &a, T b) { S B = (S)b; if (B > a) {a = B; return 1;} return 0; } tcc(S,T) S min(S a, T b) { S c = a; updmin(c, b); return c; } tcc(S,T) S max(S a, T b) { S c = a; updmax(c, b); return c; } // witness bool witness(LL a, ll d, ll m) { LL x = LL::exp(a,m); if (x==LL(1)) return 1; F0(r,d) { if (x==LL(-1)) return 1; x = x*x; } return 0; } // O(log^3 n) test bool isPrime(ll x) { if (x < T6) { int j = 2; while (j*j <= x) { if (x%j==0) return 0; ++j; } return 1; } ll d = 0; ll m = 0; ll y = x; ll cur = LL::m; LL::m = x; bool ret = 1; while (y>>=1) { ++d; if (y&1) break; } m = y; if (x < 1e12) { ret = witness(2,d,m) && witness(13,d,m) && witness(23,d,m) && witness(1662803,d,m); } else { ret = witness(2,d,m) && witness(3,d,m) && witness(5,d,m) && witness(7,d,m) && witness(11,d,m) && witness(13,d,m) && witness(17,d,m) && witness(19,d,m) && witness(23,d,m) && witness(29,d,m) && witness(31,d,m) && witness(37,d,m) && witness(41,d,m); } LL::m = cur; return ret; } #define H H5 #define HH 43 ll gcd(ll a, ll b) { return b?gcd(b, a % b):a; } void precalc() { } void reset() { } bool cmp(pii a, pii b) { return (a.s==b.s)?(a.f<b.f):(a.s<b.s); } bool debug = 0; struct Cheese { ll F(ll a, ll b) { return a+b; } int sz; vector<ll> ST; vector<ll> lazy; void start(int n) { sz = n; for (int i = 0; i < 4*n; i++) { ST.pb(0); lazy.pb(0); } } void build(ll * A, int idx, int b, int e) { lazy[idx]=0; if(b == e) { ST[idx] = A[b]; } else { int mid = (b + e) / 2; build(A, 2*idx, b, mid); build(A, 2*idx+1, mid+1, e); ST[idx] = F(ST[2*idx],ST[2*idx+1]); } } void build(ll * A) { build(A, 1, 0, sz-1); } void update(int idx, int b, int e, int l, int r, ll val) { if (lazy[idx] != 0) { ST[idx] += lazy[idx]; if(b != e) { lazy[idx*2] += lazy[idx]; lazy[idx*2+1] += lazy[idx]; } lazy[idx] = 0; } if ((b > e) || (b > r) || (e < l)) return; if ((b >= l) && (e <= r)) { ST[idx] += val; if (b != e) { lazy[idx*2] += val; lazy[idx*2+1] += val; } return; } int mid = (b + e) / 2; update(idx*2, b, mid, l, r, val); update(idx*2 + 1, mid + 1, e, l, r, val); ST[idx] = F(ST[idx*2],ST[idx*2+1]); } void update(int l, int r, ll val) { update(1,0,sz-1,l,r,val); } ll query(int idx, int b, int e, int l, int r) { if ((b > e) || (b > r) || (e < l)) return 0; if (lazy[idx] != 0) { ST[idx] += lazy[idx]; if (b != e) { lazy[idx*2] += lazy[idx]; lazy[idx*2+1] += lazy[idx]; } lazy[idx] = 0; } if(b >= l and e <= r) return ST[idx]; int mid = (b + e) / 2; ll p1 = query(idx*2, b, mid, l, r); ll p2 = query(idx*2 + 1, mid + 1, e, l, r); return F(p1,p2); } ll query(int l, int r) { return query(1,0,sz-1,l,r); } ll query(int l) { return query(l,l); } } ST; vector<pii> Qs; void read() { N=rd(); ST.start(H); F0(i,N) { int h = rd(); int k = rd(); Qs.pb({h,k}); } srt(Qs); FE(x,Qs) { int h = x.f; int k = x.s; int L,R,lm,rm,key; key = ST.query(h-k); L = 0, R = h-k; while (L<R) { int M = (L+R)>>1; if (ST.query(M)==key) { R = M; } else { L = M+1; } } lm=L; L = h-k, R = h-1; while (L<R) { int M = (L+R+1)>>1; if (ST.query(M)==key) { L = M; } else { R = M-1; } } rm=R; int dist = rm-(h-k); ST.update(rm+1,h-1,1); ST.update(lm,lm+dist,1); } ll ans = 0; F0(i,H) { ll k = ST.query(i); ans+=k*(k-1)/2; } cout << ans << endl; } int main() { precalc(); bool trials = 0; bool interactive = 0; if (!interactive) { ios_base::sync_with_stdio(false); cin.tie(NULL); } if (trials) cases=rd(); else cases=1; while (cases--) { read(); } }

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

sails.cpp: In function 'void ds(T*, int)':
sails.cpp:120:17: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  120 | #define F0(x,n) for(ll x = 0; x < n; ++x)
      |                 ^~~
sails.cpp:176:5: note: in expansion of macro 'F0'
  176 |     F0(i,t) ds(*(x++)); cout << endl;
      |     ^~
sails.cpp:176:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  176 |     F0(i,t) ds(*(x++)); cout << endl;
      |                         ^~~~
#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...