Submission #967777

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967777	2024-04-22T19:49:37 Z	shadow_sami	Dynamic Diameter (CEOI19_diameter)	C++17	7 / 100	155 ms	29768 KB

diameter

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
// typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
vector<pi> adj[mx];
ll c[mx];
ll dp[mx];
ll pd[mx];
ll sr,de;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>m>>tp;
        multiset<ll> st;
        fip(0,n-1){
        	cin>>sr>>de>>tptp;
        	adj[sr].push_back({de,i});
        	adj[de].push_back({sr,i});
        	c[i] = tptp;        	
        	st.insert(-tptp);
    	}
    	res = 0;
    	while(m--){
    		cin>>sr>>de;
    		sr += res;
    		sr %= (n-1);
    		de += res;
    		de %= (tp);
    		// debug(sr)
    		// debug(de);
    		if(st.find(-c[sr])!=st.end())
    			st.erase(st.find(-c[sr]));
    		c[sr] = de;
    		st.insert(-c[sr]);    	
    		ans = 0;	
    		if(st.size()){
    			// debug(st);
    			tp2 = *st.begin();
    			st.erase(st.begin());
    			ans = max(ans,-tp2);
    			if(st.size())
    				ans = max(ans,-tp2-(*st.begin()));
    			st.insert(tp2);
    		}
    		cout<<ans<<nli;    		
    		res = ans;
    	}
        
    // cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	15452 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	15452 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	15452 KB	Output is correct
2	Correct	3 ms	15452 KB	Output is correct
3	Correct	4 ms	15452 KB	Output is correct
4	Correct	13 ms	15848 KB	Output is correct
5	Correct	33 ms	15916 KB	Output is correct
6	Correct	4 ms	15452 KB	Output is correct
7	Correct	4 ms	15452 KB	Output is correct
8	Correct	4 ms	15452 KB	Output is correct
9	Correct	5 ms	15452 KB	Output is correct
10	Correct	11 ms	15708 KB	Output is correct
11	Correct	40 ms	15884 KB	Output is correct
12	Correct	5 ms	15964 KB	Output is correct
13	Correct	6 ms	15960 KB	Output is correct
14	Correct	8 ms	15964 KB	Output is correct
15	Correct	14 ms	16120 KB	Output is correct
16	Correct	58 ms	16468 KB	Output is correct
17	Correct	48 ms	26788 KB	Output is correct
18	Correct	49 ms	26816 KB	Output is correct
19	Correct	51 ms	26816 KB	Output is correct
20	Correct	83 ms	27072 KB	Output is correct
21	Correct	143 ms	29768 KB	Output is correct