제출 #867295

#제출 시각아이디문제언어결과실행 시간메모리
867295Faisal_SaqibNuclearia (CEOI15_nuclearia)C++17
15 / 100
1069 ms351672 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #include <iostream> #include <algorithm> #include <climits> #include <cmath> #include <map> #include <set> #include <iomanip> #include <vector> #include <fstream> using namespace std; #define vll vector<ll> #define sll set<ll> #define vstr vector<string> #define ll long long #define ld long double #define supra main #define pb push_back #define add insert #define rall(x) rbegin(x),rend(x) #define all(x) (x).begin(),(x).end() #define I ios_base::sync_with_stdio(false); #define Hear cin.tie(NULL); #define Shots cout.tie(NULL); #define Ratatatata ll powmod(ll a,ll b,ll modulo) { if(b==0){ return 1; } ll temp=powmod(a,b/2,modulo); if(b%2==0){ return (temp*temp)%modulo; } else{ return (a*((temp*temp)%modulo))%modulo; } } bool Prime(ll n){ if (n <= 1) return false; for (ll i = 2; i <= sqrt(n); i++) if (n % i == 0) return false; return true; } static struct FastInput { static constexpr int BUF_SIZE = 1 << 20; char buf[BUF_SIZE]; size_t chars_read = 0; size_t buf_pos = 0; FILE *in = stdin; char cur = 0; inline char get_char() { if (buf_pos >= chars_read) { chars_read = fread(buf, 1, BUF_SIZE, in); buf_pos = 0; buf[0] = (chars_read == 0 ? -1 : buf[0]); } return cur = buf[buf_pos++]; } inline void tie(int) {} inline explicit operator bool() { return cur != -1; } inline static bool is_blank(char c) { return c <= ' '; } inline bool skip_blanks() { while (is_blank(cur) && cur != -1) { get_char(); } return cur != -1; } inline FastInput& operator>>(char& c) { skip_blanks(); c = cur; return *this; } inline FastInput& operator>>(string& s) { if (skip_blanks()) { s.clear(); do { s += cur; } while (!is_blank(get_char())); } return *this; } template <typename T> inline FastInput& read_integer(T& n) { // unsafe, doesn't check that characters are actually digits n = 0; if (skip_blanks()) { int sign = +1; if (cur == '-') { sign = -1; get_char(); } do { n += n + (n << 3) + cur - '0'; } while (!is_blank(get_char())); n *= sign; } return *this; } template <typename T> inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) { return read_integer(n); } #if !defined(_WIN32) || defined(_WIN64) inline FastInput& operator>>(__int128& n) { return read_integer(n); } #endif template <typename T> inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) { // not sure if really fast, for compatibility only n = 0; if (skip_blanks()) { string s; (*this) >> s; sscanf(s.c_str(), "%lf", &n); } return *this; } } fast_input; #define cin fast_input static struct FastOutput { static constexpr int BUF_SIZE = 1 << 20; char buf[BUF_SIZE]; size_t buf_pos = 0; static constexpr int TMP_SIZE = 1 << 20; char tmp[TMP_SIZE]; FILE *out = stdout; inline void put_char(char c) { buf[buf_pos++] = c; if (buf_pos == BUF_SIZE) { fwrite(buf, 1, buf_pos, out); buf_pos = 0; } } ~FastOutput() { fwrite(buf, 1, buf_pos, out); } inline FastOutput& operator<<(char c) { put_char(c); return *this; } inline FastOutput& operator<<(const char* s) { while (*s) { put_char(*s++); } return *this; } inline FastOutput& operator<<(const string& s) { for (int i = 0; i < (int) s.size(); i++) { put_char(s[i]); } return *this; } template <typename T> inline char* integer_to_string(T n) { // beware of TMP_SIZE char* p = tmp + TMP_SIZE - 1; if (n == 0) { *--p = '0'; } else { bool is_negative = false; if (n < 0) { is_negative = true; n = -n; } while (n > 0) { *--p = (char) ('0' + n % 10); n /= 10; } if (is_negative) { *--p = '-'; } } return p; } template <typename T> inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) { return integer_to_string(n); } #if !defined(_WIN32) || defined(_WIN64) inline char* stringify(__int128 n) { return integer_to_string(n); } #endif template <typename T> inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) { sprintf(tmp, "%.17f", n); return tmp; } template <typename T> inline FastOutput& operator<<(const T& n) { auto p = stringify(n); for (; *p != 0; p++) { put_char(*p); } return *this; } } fast_output; #define cout fast_output #define int long long struct SegmentTree { int sum=0,lazy=0; SegmentTree* next[2]; int s,e; SegmentTree(int l,int r) { s=l; e=r; if(s!=e) { int mid=(s+e)/2; next[0]=new SegmentTree(s,mid); next[1]=new SegmentTree(mid+1,e); } } void push() { if(!lazy) return; sum+=(e-s+1)*lazy; if(s!=e) { next[0]->lazy+=lazy; next[1]->lazy+=lazy; } lazy=0; } void Update(int& l,int& r,int& val) { push(); if(e<l or r<s) return; if(l<=s and e<=r) { lazy+=val; push(); return; } next[0]->Update(l,r,val); next[1]->Update(l,r,val); sum=next[0]->sum+next[1]->sum; } int get(int& l,int& r) { push(); if(e<l or r<s) { return 0; } if(l<=s and e<=r) { return sum; } int ans=next[0]->get(l,r)+next[1]->get(l,r); sum=next[0]->sum+next[1]->sum; return ans; } }; SegmentTree* dif; ll n,m; void Call_Me_When_You_Want(int& l,int& r,int& cur,int& add) { if(r<l) { return; } // dif[l]+=cur; // dif[l+1]+=add; // dif[r]+=add; // dif[r+1]-=(cur+(add*(r-l))) // a[l]+=cur; // a[l+1]+=cur+add; // | += | // a[r]+=cur+(add*(r-l)) // cout<<"Adding "<<cur<<" To range "<<l<<' '<<l<<endl; dif->Update(l,l,cur); // for(int i=1;i<=m;i++) // { // cout<<dif->get(i,i)<<' ';; // } // cout<<endl; // cout<<"Adding "<<add<<" To range "<<l+1<<' '<<r<<endl; l++; dif->Update(l,r,add); l--; // for(int i=1;i<=m;i++) // { // cout<<dif->get(i,i)<<' ';; // } // cout<<endl; // cout<<"Adding "<<-1*(cur+(r-l)*add)<<" To range "<<r+1<<' '<<r+1<<endl; r++; cur+=(r-l-1)*add; cur*=-1; dif->Update(r,r,cur); cur*=-1; cur-=(r-l-1)*add; r--; // for(int i=1;i<=m;i++) // { // cout<<dif->get(i,i)<<' ';; // } // cout<<endl; } void solve() { cin>>m>>n; ll p; cin>>p; dif=new SegmentTree(1,m+1); for(int asp=0;asp<p;asp++) { ll i,j,final,add; cin>>j>>i>>final>>add; ll l=max(1ll,j-(final/add)); ll cur=final-(add*(j-l)); j--; Call_Me_When_You_Want(l,j,cur,add); j++; ll r=min(m,j+(final/add)); add*=-1; Call_Me_When_You_Want(j,r,final,add); } vll pre={0}; int one=1; for(int i=1;i<=m;i++) { pre.pb(pre.back()+dif->get(one,i)); } ll q; cin>>q; while(q--) { ll y1,x1,y2,x2; cin>>y1>>x1>>y2>>x2; ll sum=0,cell=(y2-y1+1)*(x2-x1+1); sum=pre[y2]-pre[y1-1]; ld cur=((ld)sum/(ld)cell); cur+=0.5; cout<<(ll)cur<<'\n'; } } signed supra(){ I // cout<<setprecision(1000); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); ll tqwertyuiop=1; // cin>>tqwertyuiop; for(int tp=1;tp<=tqwertyuiop;tp++) { // cout<<"Case #"<<tp<<": "; solve(); } return 0; }
#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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...