제출 #138119

#제출 시각아이디문제언어결과실행 시간메모리
138119claudy말 (IOI15_horses)C++14
17 / 100
1533 ms58004 KiB
# include "horses.h" //# pragma GCC optimize("Ofast,no-stack-protector") //# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") # pragma GCC optimize("Ofast") # pragma GCC optimization ("unroll-loops") # include "bits/stdc++.h" /* # include <ext/pb_ds/tree_policy.hpp> # include <ext/pb_ds/assoc_container.hpp> # include <ext/rope> */ std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}}; # define ll long long # define clock (clock() * 1000.0 / CLOCKS_PER_SEC) # define rc(s) return cout << s,0 # define rcg(s) cout << s;exit(0) # define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); # define db(x) cerr << #x << " = " << x << '\n' # define pb push_back # define mp make_pair # define all(s) s.begin(),s.end() # define sz(x) (int)((x).size()) # define int ll using namespace std; // 13:00 const int mod = 1e9 + 7; set<int>s,S; int fen[1 << 19],x[1 << 19],y[1 << 19],t[1 << 21],n,b[1 << 19]; void upd(int nod,int l,int r,int pos,int val) { if(l == r) { t[nod] = val; return ; } int mid = l + r >> 1; if(pos <= mid) upd(nod << 1,l,mid,pos,val); else upd(nod << 1 | 1,mid + 1,r,pos,val); t[nod] = max(t[nod << 1],t[nod << 1 | 1]); } int qry(int nod,int tl,int tr,int l,int r) { if(l > r) return 0; if(tl == l && tr == r) return t[nod]; int mid = tl + tr >> 1; return max(qry(nod << 1,tl,mid,l,min(mid,r)),qry(nod << 1 | 1,mid + 1,tr,max(mid + 1,l),r)); } void UPD(int pos,int val) { pos++; for(int i = pos;i <= n;i += (i & (-i))) { fen[i] *= val; fen[i] %= mod; } } int QRY(int pos) { pos++; int ans = 1; for(int i = pos;i;i -= (i & (-i))) { ans *= fen[i]; ans %= mod; } return ans; } int f() { auto it = --(S.end()); for(int i = 0;i <= 35;i++) { if(it != S.begin()) it--; } int pos = (*it) + 1; vector<pair<int,int>>vec; vector<int>hm; int i = pos; while(i < n) { if(x[i] == 1) { int r = *(S.upper_bound(i)) - 1; vec.pb(mp(x[i],qry(1,0,n - 1,i,r))); hm.pb(i); i = r + 1; } else { vec.pb(mp(x[i],y[i])); hm.pb(i); i++; } } for(int i = 0;i < sz(vec);i++) b[i] = 1; for(int i = 0;i < sz(vec);i++) { int j = i + 1; int prod = 1; while(j < sz(vec)) { prod *= vec[j].first; if(prod >= vec[i].second) { b[i] = 0; break; } else if(prod * vec[j].second >= vec[i].second) { b[i] = 0; } else b[j] = 0; j++; } } int f = 0; for(int i = 0;i < sz(vec);i++) { if(b[i]) f = i; } return ((vec[f].second * QRY(hm[f])) % mod); } # undef int int init(int N, int X[], int Y[]) { # define int ll n = N; S.insert(n);S.insert(-1); for(int i = 1;i <= n;i++) fen[i] = 1; for(int i = 0;i < n;i++) { x[i] = X[i]; y[i] = Y[i]; UPD(i,x[i]); if(X[i] == 1) s.insert(i); else S.insert(i); upd(1,0,n - 1,i,Y[i]); } //cout << f() << '\n'; return f(); } int pw(int val,int p) { int ans = 1; for(int i = 0;(1LL << i) <= p;i++) { if(p & (1LL << i)) { ans *= val; ans %= mod; } val *= val; val %= mod; } return ans; } # undef int int updateX(int pos, int val) { # define int ll if(x[pos] == 1) s.erase(s.find(pos)); else S.erase(s.find(pos)); if(val == 1) s.insert(pos); else S.insert(pos); UPD(pos,(val * pw(x[pos],mod - 2)) % mod); x[pos] = val; //cout << f() << '\n'; return f(); } # undef int int updateY(int pos, int val) { # define int ll upd(1,0,n - 1,pos,val); y[pos] = val; //cout << f() << '\n'; return f(); }

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

horses.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")
 
horses.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
horses.cpp: In function 'long long int qry(long long int, long long int, long long int, long long int, long long int)':
horses.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = tl + tr >> 1;
            ~~~^~~~
horses.cpp: In function 'long long int f()':
horses.cpp:104:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(int i = 0;i < sz(vec);i++) b[i] = 1;
          ^
horses.cpp:87:6: note: shadowed declaration is here
  int i = pos;
      ^
horses.cpp:105:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(int i = 0;i < sz(vec);i++)
          ^
horses.cpp:87:6: note: shadowed declaration is here
  int i = pos;
      ^
horses.cpp:126:10: warning: declaration of 'i' shadows a previous local [-Wshadow]
  for(int i = 0;i < sz(vec);i++)
          ^
horses.cpp:87:6: note: shadowed declaration is here
  int i = pos;
      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:150:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return f();
         ~^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:180:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return f();
         ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:190:10: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return f();
         ~^~
#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...