제출 #304929

#제출 시각아이디문제언어결과실행 시간메모리
304929jainbot27말 (IOI15_horses)C++17
100 / 100
996 ms79992 KiB
#include <bits/stdc++.h> // #include "horses.h" using namespace std; #define f first #define s second #define pb push_back #define ar array #define all(x) x.begin(), x.end() #define siz(x) (int)x.size() #define FOR(x, y, z) for(int x = (y); x < (z); x++) #define ROF(x, z, y) for(int x = (y-1); x >= (z); x--) #define F0R(x, z) FOR(x, 0, z) #define R0F(x, z) ROF(x, 0, z) #define trav(x, y) for(auto&x:y) using ll = long long; using vi = vector<int>; using vl = vector<long long>; using pii = pair<int, int>; using vpii = vector<pair<int, int>>; using ld = long double; template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;} template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const char nl = '\n'; const int mxN = 2e5 + 10; const int MOD = 1e9 + 7; const long long infLL = 1e18; // modulo class int add(int x, int y){ x += y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void ad(int &x, int y) {x = add(x, y);} int sub(int x, int y){ x -= y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void sb(int &x, int y) {x = sub(x, y);} int mul(int x, int y){ return ((int64_t)x * (int64_t)y) % MOD; } void ml(int &x, int y) {x = mul(x, y);} int binpow(int x, int y){ int z = 1; while(y > 0) { if(y % 2 == 1) z = mul(z, x); x = mul(x, x); y /= 2; } return z; } int inv(int x){ return binpow(x, MOD - 2); } int divide(int x, int y){ return mul(x, inv(y)); } template<class T, int X> struct segtree{ // comb(ID,b) = b T ID = 0; T comb(T a, T b) { if(X == 1) return a+b; else if(X==0) return mul(a, b); else return max(a, b); } int n; vector<T> seg; void init(int _n) { n = _n; if(X!=0)seg.assign(2*n,ID); else seg.assign(2*n, 1); } void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); } void update(T val, int p) { p++;// set val at position p seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); } T query(int l, int r) { // sum on interval [l, r] if(r == -499) { return (X?0:1); } l++; r++; r--; T ra = (X?ID:1), rb = (X?ID:1); for (l += n, r += n+1; l < r; l /= 2, r /= 2) { if (l&1) ra = comb(ra,seg[l++]); if (r&1) rb = comb(seg[--r],rb); } return comb(ra,rb); } }; int n; vi x, y, l, r; vector<ld> lg; segtree<ld, 1> lgs; segtree<int, 0> act; segtree<int, 2> ys; set<int> vals; int getANS(){ // cout << "BRUHMOMEN" << endl; auto it = vals.rbegin(); int i = 0; ld best = 0; int pos = 0; while(it!=vals.rend() && i < 35){ int _x = *it; if(_x == -500) { _x=n; if(r[_x] == -1) { i++; it++; break; } } if(ckmax(best, lgs.query(0, *it+1) + log(ys.query(l[_x], r[_x]+1)))){ pos = *it; } i++; it++; } i = pos; if(pos == -500) i=n; return mul(act.query(0, pos+1), ys.query(l[i], r[i]+1)); } int init(int _n, int _x[], int _y[]){ n = _n; x.resize(n); y.resize(n); lg.resize(n); l.resize(n+1); r.resize(n+1); lgs.init(n+1); act.init(n+1); ys.init(n+1); F0R(i, n) x[i] = _x[i]; F0R(i, n) y[i] = _y[i]; F0R(i, n){ lg[i] = log(x[i]); } F0R(i, n){ lgs.update(lg[i], i); ys.update(y[i], i); act.update(x[i], i); } int j = n; R0F(i, n){ if(x[i] == 1){ } else{ r[i] = j-1; l[i] = i; j = i; vals.insert(i); } } l[n] = 0; r[n] = -1; if(j) { r[n] = j - 1; } vals.insert(-500); int res = getANS(); return res; } int updateX(int pos, int val){ if(x[pos] == val) return getANS(); if(val == 1){ auto it = vals.find(pos); int en = (it==prev(vals.end())?n:*(next(it)))-1; if(*prev(it) != -500) r[*prev(it)] = en; else r[n] = en; vals.erase(it); } else if(x[pos] == 1){ vals.insert(pos); auto it = vals.find(pos); if(*prev(it) != -500) r[*prev(it)] = pos - 1; else r[n] = pos - 1; int en = (it==prev(vals.end())?n:*(next(it)))-1; l[pos] = pos; r[pos] = en; cout << endl; } act.update(val, pos); lgs.update(log(val), pos); x[pos]=val; return getANS(); } int updateY(int pos, int val){ ys.update(val, pos); return getANS(); } // int main(){ // int _n = 3; // int _x[] = {2, 1, 3}; // int _y[] = {3, 2, 1}; // cout << init(_n, _x, _y); // }

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

horses.cpp: In function 'int mul(int, int)':
horses.cpp:37:57: warning: conversion from 'int64_t' {aka 'long int'} to 'int' may change value [-Wconversion]
   37 | int mul(int x, int y){ return ((int64_t)x * (int64_t)y) % MOD; } void ml(int &x, int y) {x = mul(x, y);}
      |                               ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
#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...