답안 #228108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228108	2020-04-30T00:29:29 Z	caoash	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	181 ms	13176 KB

foehn_phenomena

#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef pair<int, pi> pii;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define fax(i, a) for (int i = 0; i < (a); i++)
#define f0x(i, a, b) for (int i = (a); i < (b); i++)
#define f0xd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define faxd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define memeset memset

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize

template<class T> void ckmin(T &a, T b) { a = min(a, b); }
template<class T> void ckmax(T &a, T b) { a = max(a, b); }

template <class T, int ...Ns> struct BIT {
    T val = 0;
    void upd(T v) { val += v; }
    T query() { return val; }
};
 
template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
    BIT<T,Ns...> bit[N + 1];
    template<typename... Args> void upd(int pos, Args... args) {
        for (; pos <= N; pos += (pos&-pos)) bit[pos].upd(args...);
    }
    template<typename... Args> T sum(int r, Args... args) {
        T res = 0; for (; r; r -= (r&-r)) res += bit[r].query(args...); 
        return res;
    }
    template<typename... Args> T query(int l, int r, Args... args) {
        return sum(r,args...)-sum(l-1,args...);
    }
};

namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);

    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class T, class... Ts> void re(T& t, Ts&... ts) { 
        re(t); re(ts...); 
    }

    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { fax(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { fax(i,SZ) re(a[i]); }
}

using namespace input;

namespace output {
    void pr(int x) { cout << x; }
    void pr(long x) { cout << x; }
    void pr(ll x) { cout << x; }
    void pr(unsigned x) { cout << x; }
    void pr(unsigned long x) { cout << x; }
    void pr(unsigned long long x) { cout << x; }
    void pr(float x) { cout << x; }
    void pr(double x) { cout << x; }
    void pr(ld x) { cout << x; }
    void pr(char x) { cout << x; }
    void pr(const char* x) { cout << x; }
    void pr(const string& x) { cout << x; }
    void pr(bool x) { pr(x ? "true" : "false"); }
    
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T> void pr(const T& x);
    
    template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
        pr(t); pr(ts...); 
    }
    template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
        pr("{",x.f,", ",x.s,"}"); 
    }
    template<class T> void pr(const T& x) { 
        pr("{"); // const iterator needed for vector<bool>
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
        pr("}");
    }
    
    void ps() { pr("\n"); } // print w/ spaces
    template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
    }
    
    void pc() { pr("]\n"); } // debug w/ commas
    template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
        pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
    }
    #define dbg(x...) pr("[",#x,"] = ["), pc(x);
}

using namespace output;

namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
    }
}

using namespace io;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 200005;
const ld PI = 4*atan((ld)1);

BIT<ll,MX> b;

void upd(int l, int r, ll x){
   l++; r++;
   b.upd(l,x);
   b.upd(r+1,-x);
}

ll qry(int i){
   i++;
   return b.query(1, i);
}

int main() {
   setIO(); 
   int N,Q; ll S,T; re(N,Q,S,T);
   vl a(N+1);
   fax(i,N+1){
      re(a[i]);
      upd(i,i,a[i]);
   }
   ll sum = 0; 
   f0x(i,1,N+1){
      sum += (a[i] <= a[i-1] ? (T*(a[i-1]-a[i])) : (S * (a[i-1]-a[i]))); 
   }
   fax(i,Q){
      int l,r; re(l,r);
      ll x; re(x);
      ll pengsoo = qry(l); ll is = qry(l-1); ll the = qry(r); ll best = qry(r+1);
      if(l > 0){
        sum -= (pengsoo <= is) ? (T*(is-pengsoo)) : (S*(is-pengsoo)); 
      }
      if(r < N){
        sum -= (best <= the) ? (T*(the-best)) : (S*(the-best));
      }
      upd(l,r,x);
      /*
      fax(i,N+1){
         pr(qry(i), " ");
      }
      ps();
      */
      pengsoo = qry(l); is = qry(l-1); the = qry(r); best = qry(r+1);
      if(l > 0){
        sum += (pengsoo <= is) ? (T*(is-pengsoo)) : (S*(is-pengsoo)); 
      }
      if(r < N){
        sum += (best <= the) ? (T*(the-best)) : (S*(the-best));
      }
      //dbg(l,r,x,sum);
      pr(sum, "\n");
   }
}

Compilation message

foehn_phenomena.cpp: In function 'void io::setIn(std::__cxx11::string)':
foehn_phenomena.cpp:133:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp: In function 'void io::setOut(std::__cxx11::string)':
foehn_phenomena.cpp:134:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	512 KB	Output is correct
2	Correct	6 ms	512 KB	Output is correct
3	Correct	6 ms	512 KB	Output is correct
4	Correct	6 ms	512 KB	Output is correct
5	Correct	6 ms	512 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	512 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct
11	Correct	6 ms	512 KB	Output is correct
12	Correct	6 ms	512 KB	Output is correct
13	Correct	6 ms	512 KB	Output is correct
14	Correct	6 ms	512 KB	Output is correct
15	Correct	6 ms	512 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	6 ms	512 KB	Output is correct
19	Correct	5 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	5232 KB	Output is correct
2	Correct	175 ms	5940 KB	Output is correct
3	Correct	167 ms	6392 KB	Output is correct
4	Correct	170 ms	5496 KB	Output is correct
5	Correct	166 ms	6392 KB	Output is correct
6	Correct	139 ms	6776 KB	Output is correct
7	Correct	133 ms	6648 KB	Output is correct
8	Correct	162 ms	6648 KB	Output is correct
9	Correct	164 ms	7032 KB	Output is correct
10	Correct	165 ms	5752 KB	Output is correct
11	Correct	133 ms	6776 KB	Output is correct
12	Correct	131 ms	7160 KB	Output is correct
13	Correct	139 ms	11960 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	512 KB	Output is correct
2	Correct	6 ms	512 KB	Output is correct
3	Correct	6 ms	512 KB	Output is correct
4	Correct	6 ms	512 KB	Output is correct
5	Correct	6 ms	512 KB	Output is correct
6	Correct	6 ms	512 KB	Output is correct
7	Correct	6 ms	512 KB	Output is correct
8	Correct	6 ms	512 KB	Output is correct
9	Correct	6 ms	512 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct
11	Correct	6 ms	512 KB	Output is correct
12	Correct	6 ms	512 KB	Output is correct
13	Correct	6 ms	512 KB	Output is correct
14	Correct	6 ms	512 KB	Output is correct
15	Correct	6 ms	512 KB	Output is correct
16	Correct	6 ms	512 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	6 ms	512 KB	Output is correct
19	Correct	5 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Correct	171 ms	5232 KB	Output is correct
23	Correct	175 ms	5940 KB	Output is correct
24	Correct	167 ms	6392 KB	Output is correct
25	Correct	170 ms	5496 KB	Output is correct
26	Correct	166 ms	6392 KB	Output is correct
27	Correct	139 ms	6776 KB	Output is correct
28	Correct	133 ms	6648 KB	Output is correct
29	Correct	162 ms	6648 KB	Output is correct
30	Correct	164 ms	7032 KB	Output is correct
31	Correct	165 ms	5752 KB	Output is correct
32	Correct	133 ms	6776 KB	Output is correct
33	Correct	131 ms	7160 KB	Output is correct
34	Correct	139 ms	11960 KB	Output is correct
35	Correct	163 ms	10488 KB	Output is correct
36	Correct	180 ms	11900 KB	Output is correct
37	Correct	178 ms	12664 KB	Output is correct
38	Correct	172 ms	12536 KB	Output is correct
39	Correct	181 ms	12536 KB	Output is correct
40	Correct	169 ms	12536 KB	Output is correct
41	Correct	170 ms	12408 KB	Output is correct
42	Correct	171 ms	12408 KB	Output is correct
43	Correct	168 ms	11768 KB	Output is correct
44	Correct	176 ms	12152 KB	Output is correct
45	Correct	164 ms	12152 KB	Output is correct
46	Correct	172 ms	13176 KB	Output is correct
47	Correct	133 ms	11768 KB	Output is correct
48	Correct	141 ms	11896 KB	Output is correct
49	Correct	158 ms	10872 KB	Output is correct
50	Correct	134 ms	11512 KB	Output is correct
51	Correct	144 ms	11944 KB	Output is correct
52	Correct	141 ms	11896 KB	Output is correct