제출 #392872

#제출 시각아이디문제언어결과실행 시간메모리
392872arwaeystoamneg말 (IOI15_horses)C++17
17 / 100
1094 ms45540 KiB
// EXPLOSION! #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> #include<unordered_set> #include<unordered_map> #include<chrono> using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pair<int, int>> vpi; typedef vector<pair<ll, ll>> vpll; #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define trav(a,x) for (auto& a: x) #define pb push_back #define mp make_pair #define rsz resize #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define f first #define s second #define cont continue #define endl '\n' //#define ednl '\n' #define test int testc;cin>>testc;while(testc--) #define pr(a, b) trav(x,a)cerr << x << b; cerr << endl; #define message cout << "Hello World" << endl; const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!! const ll linf = 4000000000000000000LL; const ll inf = 1000000007;//998244353 void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; } }void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; } void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); if (sz(s)) { freopen((s + ".in").c_str(), "r", stdin); if (s != "test1") freopen((s + ".out").c_str(), "w", stdout); } } template<int MOD, int RT> struct mint { static const int mod = MOD; static constexpr mint rt() { return RT; } // primitive root for FFT int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int mint() { v = 0; } mint(ll _v) { v = int((-MOD < _v&& _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; } friend bool operator==(const mint& a, const mint& b) { return a.v == b.v; } friend bool operator!=(const mint& a, const mint& b) { return !(a == b); } friend bool operator<(const mint& a, const mint& b) { return a.v < b.v; } mint& operator+=(const mint& m) { if ((v += m.v) >= MOD) v -= MOD; return *this; } mint& operator-=(const mint& m) { if ((v -= m.v) < 0) v += MOD; return *this; } mint& operator*=(const mint& m) { v = int((ll)v * m.v % MOD); return *this; } mint& operator/=(const mint& m) { return (*this) *= inv(m); } friend mint power(mint a, ll p) {// MAKE SURE YOU ARE USING THE CORRECT VERSION OF POW!!!!!!!! mint ans = 1; assert(p >= 0); for (; p; p /= 2, a *= a) if (p & 1) ans *= a; return ans; } friend mint inv(const mint& a) { assert(a.v != 0); return power(a, MOD - 2); } mint operator-() const { return mint(-v); } mint& operator++() { return *this += 1; } mint& operator--() { return *this -= 1; } friend mint operator+(mint a, const mint& b) { return a += b; } friend mint operator-(mint a, const mint& b) { return a -= b; } friend mint operator*(mint a, const mint& b) { return a *= b; } friend mint operator/(mint a, const mint& b) { return a /= b; } }; template<class T>class segment_tree { struct item { T sum; }; item single(T i) { return { i }; } item merge(item x, item y) { item ans; ans.sum = max(x.sum, y.sum); return ans; } vector<item> tree; vector<item>A; int height; item neutral = { 0 }; public:void build(vector<T>& B) { int n = B.size(); height = log2(n + 1) + 1; A.rsz(n); tree.rsz((1 << height + 1) - 1); F0R(i, n)A[i] = single(B[i]); A.rsz(1 << height, neutral); build(A, 0, 0, (1 << height) - 1); } void build(vector<item>& A, int v, int tl, int tr) { if (tl == tr) tree[v] = A[tl]; else { int mid = (tl + tr) / 2; build(A, 2 * v + 1, tl, mid); build(A, 2 * v + 2, mid + 1, tr); tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]); } } public:T query(int l, int r) { return query(0, 0, (1 << height) - 1, l, r).sum; } item query(int v, int tl, int tr, int l, int r) { if (r<tl || l>tr)return neutral; if (l <= tl && r >= tr) { return tree[v]; } int mid = (tl + tr) / 2; return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r)); } //assign public:void update(int pos, T val) { update(0, 0, (1 << height) - 1, pos, single(val)); } void update(int v, int tl, int tr, int pos, item val) { if (tl == tr) { tree[v] = val; } else { int mid = (tl + tr) / 2; if (pos <= mid) update(2 * v + 1, tl, mid, pos, val); else update(2 * v + 2, mid + 1, tr, pos, val); tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]); } } }; typedef mint<inf, 5> mi; #ifndef arwaeystoamneg #include "horses.h" #endif const int MAX_N = 500005, MAX_V = 1000000000; int n, a[MAX_N]; segment_tree<int>best; mi prod; struct T { int x; int l, r; }; map<int, T>active; int query() { auto it = active.end(); pair<ll, int>ans = { -MAX_V,-1 }; ll cur = 1; mi t = prod; while (it != active.begin()) { it--; t *= inv((mi)it->s.x); cur *= it->s.x; if (cur > MAX_V) { t *= it->s.x; it++; break; } } cur = 1; while (it != active.end()) { int v = best.query(it->s.l, it->s.r); t *= it->s.x; cur *= it->s.x; ans = max(ans, { cur * v ,(int)(t * v) }); it++; } return ans.s; } int init(int N, int X[], int Y[]) { n = N; F0R(i, n)a[i] = X[i]; vi t(n); F0R(i, n)t[i] = Y[i]; best.build(t); prod = 1; F0R(i, n)prod *= X[i]; int last = 0; FOR(i, 1, n) { if (X[i] == 1) { } else { active.insert({ last,{X[last],last,i - 1} }); last = i; } } active.insert({ last,{X[last],last,n - 1} }); return query(); } int updateX(int pos, int val) { if (val == 1) { if (a[pos] == 1) { } else if (pos == 0) { active.begin()->s.x = 1; } else { auto it = active.find(pos); int r = it->s.r; it--; it->s.r = r; it++; active.erase(it); } } else { if (a[pos] == 1 && pos) { // 0 is always in active so there will always be a -- auto it = active.upper_bound(pos); it--; int r = it->s.r;// please it->s.r = pos - 1;// dont be the only reason why this was wrong active.insert({ pos, {val,pos,r} }); } else { active[pos].x = val; } } prod *= inv((mi)a[pos]); prod *= val; a[pos] = val; return query(); } int updateY(int pos, int val) { best.update(pos, val); return query(); } #ifdef arwaeystoamneg int main() { setIO("test1"); int N; cin >> N; int* X = (int*)malloc(sizeof(int) * (unsigned int)N); int* Y = (int*)malloc(sizeof(int) * (unsigned int)N); for (int i = 0; i < N; i++) { cin >> X[i]; } for (int i = 0; i < N; i++) { cin >> Y[i]; } cout << init(N, X, Y) << endl; int M; cin >> M; for (int i = 0; i < M; i++) { int type; int pos; int val; cin >> type >> pos >> val; if (type == 1) { cout << updateX(pos, val) << endl; } else if (type == 2) { cout << updateY(pos, val) << endl; } } return 0; } #endif

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

horses.cpp: In member function 'void segment_tree<T>::build(std::vector<segment_tree<T>::item>&, int, int, int)':
horses.cpp:134:4: warning: declaration of 'A' shadows a member of 'segment_tree<T>' [-Wshadow]
  134 |    {
      |    ^
horses.cpp:120:14: note: shadowed declaration is here
  120 |  vector<item>A;
      |              ^
horses.cpp: In instantiation of 'void segment_tree<T>::build(std::vector<_Tp>&) [with T = int]':
horses.cpp:230:14:   required from here
horses.cpp:125:6: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  125 |  int n = B.size();
      |      ^
horses.cpp:126:23: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
  126 |  height = log2(n + 1) + 1;
      |           ~~~~~~~~~~~~^~~
horses.cpp:128:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  128 |  tree.rsz((1 << height + 1) - 1);
      |                 ~~~~~~~^~~
horses.cpp: In instantiation of 'void segment_tree<T>::build(std::vector<segment_tree<T>::item>&, int, int, int) [with T = int]':
horses.cpp:131:2:   required from 'void segment_tree<T>::build(std::vector<_Tp>&) [with T = int]'
horses.cpp:230:14:   required from here
horses.cpp:133:9: warning: declaration of 'A' shadows a member of 'segment_tree<int>' [-Wshadow]
  133 |    void build(vector<item>& A, int v, int tl, int tr)
      |         ^~~~~
horses.cpp:120:14: note: shadowed declaration is here
  120 |  vector<item>A;
      |              ^
horses.cpp: In function 'void setIO(std::string)':
horses.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
horses.cpp:50:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...