Submission #918916

#TimeUsernameProblemLanguageResultExecution timeMemory
918916mychecksedadDeda (COCI17_deda)C++17
140 / 140
168 ms50512 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, q, T[N], idx1[N], idx2[N]; vector<int> v[N]; void build(int l, int r, int k){ // cout << k << ' ' << l << ' ' << r << '\n'; if(l == r){ idx1[k] = l, idx2[k] = r; T[k] = MOD; return; } int m = l+r>>1; build(l, m, k<<1); build(m+1, r, k<<1|1); T[k] = MOD; idx1[k] = l, idx2[k] = r; } void upd(int l, int r, int p, int k, int val){ if(l == r){ T[k] = val; return; } int m = l+r>>1; if(p <= m) upd(l, m, p, k<<1, val); else upd(m+1, r, p, k<<1|1, val); T[k] = min(T[k<<1], T[k<<1|1]); } int get2(int l, int r, int k, int val){ if(l == r) return l; int m = l+r>>1; if(T[k<<1] <= val) return get2(l, m, k<<1, val); return get2(m+1, r, k<<1|1, val); } int get(int p, int val){ for(auto &idx: v[p]){ // cout << idx if(T[idx] <= val){ return get2(idx1[idx], idx2[idx], idx, val); } } return -1; } void s(int l, int r, int p, int k){ if(l == r){ v[p].pb(k); return; } int m = l+r>>1; if(p <= m){ v[p].pb(k<<1|1); s(l, m, p, k<<1); }else s(m+1, r, p, k<<1|1); } void solve(){ cin >> n >> q; build(1, n, 1); for(int i = 1; i <= n; ++i){ s(1, n, i, 1); // cout << i << ":\n"; // for(int j : v[i]) cout << j << ' '; // en; sort(all(v[i]), [&](const int &x, const int &y){ return idx1[x] < idx1[y]; }); } for(int i = 0; i < q; ++i){ char c; cin >> c; if(c == 'M'){ int X, A; cin >> X >> A; upd(1, n, A, 1, X); }else{ int B, Y; cin >> Y >> B; cout << get(B, Y) << '\n'; } } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

deda.cpp: In function 'void build(int, int, int)':
deda.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int m = l+r>>1;
      |           ~^~
deda.cpp: In function 'void upd(int, int, int, int, int)':
deda.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |   int m = l+r>>1;
      |           ~^~
deda.cpp: In function 'int get2(int, int, int, int)':
deda.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int m = l+r>>1;
      |           ~^~
deda.cpp: In function 'void s(int, int, int, int)':
deda.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int m = l+r>>1;
      |           ~^~
deda.cpp: In function 'int main()':
deda.cpp:91:15: warning: unused variable 'aa' [-Wunused-variable]
   91 |   int tt = 1, aa;
      |               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...