Submission #886137

#TimeUsernameProblemLanguageResultExecution timeMemory
886137nnhzzzSum Zero (RMI20_sumzero)C++14
0 / 100
3 ms6744 KiB
/* [Author: Nguyen Ngoc Hung] - From THPT Ngo Gia Tu with Love */ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <locale> #include <map> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <unordered_set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <valarray> #include <vector> #include <cstring> #include <unordered_map> #include <cmath> #include <array> #include <cassert> #include <random> #include <chrono> using namespace std; #define __nnhzzz__ signed main() #define BIT(i,j) ((i>>j)&1LL) #define MASK(i) (1LL<<(i)) #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define _PB push_back #define fi first #define se second #define ll long long #define ld long double #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define pii pair<int,int> #define vpii vector<pii> #define vvpii vector<vpii> #define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j) #define REPD(i,be,en) for(int i = (be); i>=(en); i--) #define REP(i,be,en) for(int i = (be); i<=(en); i++) #define endl "\n" #define MP make_pair #define int ll //-----------------------------------------------------------------------------------------------// int readInt(){ char c; do{ c = getchar(); }while(c!='-' && !isdigit(c)); bool neg = (c=='-'); int res = neg?0:c-'0'; while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0'); return neg?-res:res; } //------------------------------------------------------------------------------------------------// const ll LINF = 1e18; const int INF = 1e9; const int LOG = 17; const int MAXN = 5e5+7; const int N = 1e2+3; const int MOD = 1e9+7; const int BASE = 1e5; const ld EPS = 1e-9; const ld PI = acos(-1); const int OFFSET = 1e3; //------------------------------------------------------------------------------------------------// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;} template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;} template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; } template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; } //------------------------------------------------------------------------------------------------// /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Nguyen Ngoc Hung - nnhzzz Training for VOI24 gold medal ---------------------------------------------------------------- */ int a[MAXN]; pii q[MAXN]; int n,query; namespace sub1{ void solve(){ REP(t,1,query){ int l = q[t].fi,r = q[t].se; set<int> s; s.insert(0); int sum = 0,res = 0; REP(i,l,r){ sum += a[i]; if(s.find(sum)!=s.end()){ s.clear(); s.insert(0); sum = 0; ++res; }else{ s.insert(sum); } } cout << res << endl; } } } namespace sub2{ int f[MAXN][LOG]; void solve(){ map<int,int> mp; int sum = 0; REP(i,1,n) sum += a[i]; f[n+1][0] = n+1; int MIN = n+1; REPD(i,n,0){ f[i][0] = mp.count(sum)?mp[sum]:n+1; mini(MIN,f[i][0]); mp[sum] = i; sum -= a[i]; mini(f[i][0],MIN); } REP(j,1,LOG){ REP(i,0,n+1){ f[i][j] = f[f[i][j-1]][j-1]; } } REP(t,1,query){ int l = q[t].fi-1,r = q[t].se,res = 0; REPD(i,LOG-1,0){ if(f[l][i]<=r){ res += MASK(i); l = f[l][i]; } } cout << res << endl; } } } namespace sub3{ void solve(){ } } void solve(){ cin >> n; REP(i,1,n) cin >> a[i]; cin >> query; REP(t,1,query) cin >> q[t].fi >> q[t].se; sub2::solve(); return ; if(n<=5000 && query<=5000){ sub1::solve(); return ; } if(n<=100000 && query<=100000){ sub2::solve(); return ; } sub3::solve(); } __nnhzzz__{ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "test" if(fopen(task".inp","r")){ freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } #define task1 "nnhzzz" if(fopen(task1".inp","r")){ freopen(task1".inp","r",stdin); freopen(task1".out","w",stdout); } int test = 1; while(test--){ solve(); } cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n"; return 0; } /** /\_/\ * (= ._.) * / >TL \>AC **/

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:191:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:195:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:196:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...