QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#271399#7733. Cool, It’s Yesterday Four Times MoreThe_OwlsWA 6ms3648kbC++2012.0kb2023-12-02 11:34:042023-12-02 11:34:04

Judging History

你现在查看的是最新测评结果

  • [2023-12-02 11:34:04]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：3648kb
查看
  • [2023-12-02 11:34:04]
  • 提交

answer

#include<bits/stdc++.h>
#include<chrono>
#define FAST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(s) s.begin(),s.end()
#define gcd            __gcd
#define setbits(x)     __builtin_popcountll(x)
#define binarystring(n,x) bitset<n> (x).to_string()
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define MOD            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define pb             push_back
#define lb             lower_bound
#define ub             upper_bound
#define mk             make_pair
#define deci(x, y)     fixed<<setprecision(y)<<x
#define PI             3.141592653589793238
#define mem0(x)        memset(x,0,sizeof x)
#define mem1(x)        memset(x,-1,sizeof x)
#define pr             pair<int,int>
#define vi             vector<int>
#define vll            vector<ll>
#define vvi            vector<vi>
#define vpr            vector<pr> 
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
using namespace std;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
           // http://xorshift.di.unimi.it/splitmix64.c
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
           return x ^ (x >> 31);
        }
        size_t operator()(uint64_t x) const {
           static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
};
#define nline '\n'
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<' '; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << '{'; _print(p.first); cerr << ','; _print(p.second); cerr << '}';}
template <class T> void _print(vector <T> v) {cerr << '['; for (T i : v) {_print(i); cerr << ' ';} cerr << ']';}
template <class T> void _print(set <T> v) {cerr << '['; for (T i : v) {_print(i); cerr << ' ';} cerr << ']';}
template <class T> void _print(multiset <T> v) {cerr << '['; for (T i : v) {_print(i); cerr << ' ';} cerr << ']';}
template <class T, class V> void _print(map <T, V> v) {cerr << '['; for (auto i : v) {_print(i); cerr << ' ';} cerr << ']';}
class Mint
{
//WARNING:
//Be very careful not to use two Mints with different mods for any operation
//No guarantee of behavior in this case
public:
ll val;
static ll mod_exp(ll a, ll b){ ll res=1;   a=a%MOD; while(b>0){ if(b%2==1) res=(res*a)%MOD; b/=2; a=(a*a)%MOD; } return res; }
static ll gcdExtended(ll a, ll b, ll *x, ll *y) { if (a == 0) { *x = 0, *y = 1; return b; } ll x1, y1; ll gcd = gcdExtended(b%a, a, &x1, &y1);*x = y1 - (b/a) * x1; *y = x1; return gcd; }
static ll modInverse(ll a) { ll x, y; 	ll g = gcdExtended(a, MOD, &x, &y); g++; ll res = (x%MOD);	if(res < 0) res += MOD;	return res;} 
Mint(){	val = 0;} 
Mint(ll x){	val = x%MOD;	if(val < 0) val += MOD;}
Mint& operator +=(const Mint &other){	val += other.val;	if(val >= MOD) val -= MOD; return (*this); }
Mint& operator -=(const Mint &other){   val -= other.val;if(val < 0) val += MOD;  return (*this); }
Mint& operator *=(const Mint &other){	val = (val * other.val)%MOD; return (*this); }
Mint& operator /=(const Mint &other){	val = (val * modInverse(other.val)) % MOD; return (*this); }
Mint& operator =(const Mint &other) { 	val = other.val; return (*this); }
Mint operator +(const Mint &other) const {	return Mint(*this) += other; }
Mint operator -(const Mint &other) const {	return Mint(*this) -= other; }
Mint operator *(const Mint &other) const {	return Mint(*this) *= other; }
Mint operator /(const Mint &other) const {	return Mint(*this) /= other; }
bool operator ==(const Mint &other) const {   return val == other.val; }
Mint operator ++() { ++val; if(val == MOD) val = 0; return (*this); }
Mint operator ++(int) { val++; if(val == MOD) val = 0; return Mint(val-1); }
Mint operator --() { --val; if(val == -1) val = MOD-1; return (*this); }
Mint operator --(int) { val--; if(val == -1) val = MOD-1; return Mint(val+1); }
// ^ has very low precedence, careful!!
template<typename T>
Mint& operator ^=(const T &other){   val = mod_exp(val, other); return (*this); }
template<typename T>
Mint operator ^(const T &other) const {  return Mint(*this) ^= other; }
Mint& operator ^=(const Mint &other){   val = mod_exp(val, other.val); return (*this); }
Mint operator ^(const Mint &other) const {  return Mint(*this) ^= other; }
template<typename T>
explicit operator T() {	return (T)val; }
template<typename T>
friend Mint operator +(T other, const Mint &M){	return Mint(other) + M; }
template<typename T>
friend Mint operator -(T other, const Mint &M){	return Mint(other) - M; }
template<typename T>
friend Mint operator *(T other, const Mint &M){	return Mint(other) * M; }
template<typename T>
friend Mint operator /(T other, const Mint &M){	return Mint(other) / M; }
template<typename T>
friend Mint operator ^(T other, const Mint &M){	return Mint(other) ^ M; }
friend std::ostream &operator << (std::ostream &output, const Mint &M){  return output << M.val; }
friend std::istream &operator >> (std::istream &input, Mint &M) { input >> M.val;	M.val %= MOD;	return input;}};




ll BinExpItr(ll a , ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=(res*a)%mod;
        }
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
struct water{
    int size;
    vll operations;
    vll sums;
    ll NO_OPERATIONS = LLONG_MIN;
    ll Neutral_Element= 0; 
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        sums.assign(2*size,0);
        operations.assign(2*size,0);
    }
    ll modify_Op(ll a , ll b , ll len){
        if(b ==  NO_OPERATIONS) return a;
        return b*len;
    }
    void apply_mod_op(ll &a , ll b , ll len){
        a=modify_Op(a,b,len);
    }
    ll calc_Op(ll a , ll b){
        return a+b ;
    }
    void propagate(int x , int lx ,int rx){
        if(rx - lx == 1) return;
        int m = (lx + rx )/2;
 
        apply_mod_op(sums[2*x+1], operations[x]  , m -lx);
        apply_mod_op(sums[2*x+2] , operations[x] , rx -m );
        apply_mod_op(operations[2*x+2] , operations[x] , 1 );
        apply_mod_op(operations[2*x+1] , operations[x] , 1  );
        operations[x]=NO_OPERATIONS;
 
    }
    void modify (int l , int r , int v, int x , int lx , int rx){
        propagate(x , lx , rx );
        if(lx>=r || l>=rx) return ;
        if(lx >= l && rx <= r){
            apply_mod_op(operations[x] , v , 1 ) ;
            apply_mod_op(sums[x] ,  v , rx-lx) ;
            return;
        }
        int m  = (lx+rx)/2;
        modify(l,r,v,2*x+1,lx,m);modify(l,r,v,2*x+2,m,rx);
        sums[x]=calc_Op(sums[2*x+1], sums[2*x+2] );
        apply_mod_op(sums[x], operations[x],rx-lx);
    }
    void modify (int l ,int r , int v){
        modify(l , r , v , 0 , 0 , size);
    }
    ll calc(int l ,int r , int x , int lx ,int rx){
        propagate(x,lx,rx);
        if(lx>=r || rx<=l) return Neutral_Element;
        if(lx>=l && rx<=r){
            return sums[x];
        }
        int m = (lx+rx)/2;
        auto m1 = calc(l,r,2*x+1, lx , m);
        auto m2 = calc(l,r, 2*x+2 , m , rx);
        auto res = calc_Op(m1,m2);
      
        return res;
    }
    ll calc (int l , int r ){
        return calc(l,r , 0 , 0 ,size);
    }
    void build(vector<ll> &a,int x , int lx , int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                sums[x]=a[lx];
            }
            return;
        }
        else{
            int m = (lx+rx)/2;
            build(a,2*x+1,lx,m);
            build(a,2*x+2,m,rx);
        }
        sums[x]=calc_Op(sums[2*x+1],sums[2*x+2]);
    }
    void build(vector<ll> &a){
        build(a,0,0,size);
    }
};

struct height{
    int size;
    vll sums;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        sums.assign(2*size,0);
    }
    void build(vector<ll> &a,int x , int lx , int rx){
        if(rx-lx==1){
            if(lx<(int)a.size()){
                sums[x]=a[lx];
            }
            return;
        }
        else{
            int m = (lx+rx)/2;
            build(a,2*x+1,lx,m);
            build(a,2*x+2,m,rx);
        }
        sums[x]=max(sums[2*x+1],sums[2*x+2]);
    }
    void build(vector<ll> &a){
        build(a,0,0,size);
    }
    void set(int i , int v , int x , int lx, int rx){
        if(rx-lx==1){
            sums[x] += v;
            return;
        }
        int m = (lx+rx)/2;
        if(i<m){
            set(i,v,2*x+1,lx,m);
        }
        else{
            set(i,v,2*x+2,m,rx);
        }
        sums[x]=max(sums[2*x+1],sums[2*x+2]);
    }
    ll calc(int m , ll v , water &w , int n){
        w.modify(m , m + 1, v);
        ll lx = m + 1, rx = n , mid , ans = -1 , ind = -1;
        ll upper = min(v , sum(m + 1 , n));
        while(lx <= rx){
            mid = (lx + rx)/2;
            if(sum(m + 1, mid) < upper){
                ind = mid;
                lx = mid + 1;
            }
            else rx = mid - 1;
        }
        if(ind != n )
        w.modify(m + 1, ind , min(upper , sum(m + 1 , ind + 1)));
        lx = 0; rx = m ; ans = -1; ind = -1;
        upper = min(v , sum(0 , m));
        while(lx <= rx){
            mid = (lx + rx)/2;
            if(sum(mid , m ) < upper){
                ind = mid;
                rx = mid - 1;
            }
            else lx = mid + 1;
        }
        if(ind != 0)
        w.modify(ind , m , min(upper , sum(ind - 1, m)));
        return w.calc(0 , n);
    }
    void set(int i , ll v){
        set(i,v,0,0,size);
    }
    ll sum(int l , int r, int x , int lx , int rx){
        if(l>=rx || lx>=r) return 0;
        if(l<=lx && r>=rx) return sums[x]; 
        int m = (lx+rx)/2;
        ll s1=sum(l,r,2*x+1,lx,m);
        ll s2=sum(l,r,2*x+2,m,rx);
        return max(s1,s2);
        
    }
    ll sum(int l , int r){
        return sum(l,r,0,0,size);
    }
};

void solve(){
    int n;
    cin >> n;
    ll sum = 0;
    vll a(n);
    for(auto &x  : a) cin >> x , sum += x;
    height h;
    h.init(n);
    h.build(a);
    water w;
    w.init(n);
    vector<ll> ngr(n , -1) , ngl(n , -1);
    stack<int> st;
    for(int i = 0 ; i < n ; i++){
        while(!st.empty() && st.top() < a[i]) st.pop();
        if(!st.empty()) {
            ngl[i] = st.top();
            if(st.top() < a[i]) st.push(a[i]);
        }
        else st.push(a[i]);
    }
    while(!st.empty()) st.pop();
    for(int i = n-1 ; i > -1 ; i--){
        while(!st.empty() && st.top() < a[i]) st.pop();
        if(!st.empty()) {
            ngr[i] = st.top();
            if(st.top() < a[i]) st.push(a[i]);
        }
        else st.push(a[i]);
    }
    vector<ll> wat(n);
    for(int i = 0; i < n ; i++){
        wat[i] =  max(a[i] , min(ngl[i],ngr[i]));
        w.modify(i , i + 1 , wat[i]);
    }
    int q;
    cin >> q;
    for(int i = 0 ; i < q; i++){
        int x , v;
        cin >> x >> v;
        --x;
        h.set(x , v);
        sum += v;
        if(w.calc(x , x + 1) < h.sum(x , x + 1)){
            cout << h.calc(x , h.sum(x , x + 1) , w , n ) - sum << nline;
        }
        else cout << w.calc(0 , n) - sum << nline;
    }
}
int main(){
    FAST
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 3648kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

-5
-10
-15
-20
-25
-30
-35
-40
-45
-50
-55
-60
-65
-70
-75
-80
-85
-90
-95
-100
-105
-110
-115
-120
-125
-130
-135
-140
-145
-150
-155
-160
-165
-170
-175
-180
-185
-190
-195
-200
-205
-210
-215
-220
-225
-230
-235
-240
-245
-250
-255
-260
-265
-270
-275
-280
-285
-290
-295
-300
-305
-310
-315
-320
...

result:

wrong answer 1st lines differ - expected: '3', found: '-5'
English 繁體中文 简体中文

服务器时间: 2024-12-05 02:08:59 | 开源项目