Submission #1196915

#TimeUsernameProblemLanguageResultExecution timeMemory
1196915YassirSalama가로등 (APIO19_street_lamps)C++20
20 / 100
279 ms30884 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define int long long using ull=unsigned long long; using ll=long long; using pii=pair<int,int>; const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; const int mod=1e9+7; #define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n"; template <typename T> istream& operator>>(istream& is, vector<T> &a) { copy_n(istream_iterator<T>(is), a.size(), a.begin()); return is;} #ifdef IOI template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } void dbg_out() { cout << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); } #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__); #else #define dbg(...) 1337; #endif #define pb push_back #define F first #define S second #define all(v) v.begin(),v.end() struct Node{ int mx; int sum; Node* left,*right; Node() : mx(0),sum(0),left(nullptr),right(nullptr) {} }; Node* root=new Node(); void update(Node* node,int l,int r,int ql,int x){ if(l==r){ node->mx=x; node->sum=x; return; } int mid=(l+r)/2; if(ql<=mid){ if(node->left==nullptr) node->left=new Node(); update(node->left,l,mid,ql,x); }else{ if(node->right==nullptr) node->right=new Node(); update(node->right,mid+1,r,ql,x); } node->sum=(node->left?node->left->sum:0LL)+(node->right?node->right->sum:0LL); node->mx=max((node->left?node->left->mx:0LL),(node->right?node->right->mx:0LL)); } int querymx(Node* node,int l,int r,int ql,int qr){ if(!node) return 0; if(ql<=l&&r<=qr) return node->mx; int mid=(l+r)/2; int ans=0; if(ql<=mid&&node->left) ans=max(ans,querymx(node->left,l,mid,ql,qr)); if(qr>mid&&node->right) ans=max(ans,querymx(node->right,mid+1,r,ql,qr)); return ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin>>n; int q; cin>>q; string s; cin>>s; Node* root = new Node(); for(int i = 0;i<n;i++){ if(s[i]=='1'){ update(root,0,n-1,i,0); }else{ update(root,0,n-1,i,1e18); } } for(int j =1;j<=q;j++){ string a; cin>>a; if(a[0]=='t'){ int i; cin>>i; i--; int x = s[i]-'0'; x^=1; if(x==1){ update(root,0,n-1,i,j); } }else{ int a,b; cin>>a>>b; a--,b--;b--; int x = querymx(root,0,n-1,a,b); int ans = j-x; ans = max(ans,0LL); cout<<ans<<endl; } } }
#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...