oj.uz

Submission #97430

# Submission time Handle Problem Language Result Execution time Memory
97430 2019-02-16T01:41:13 Z updown1 Kralj (COCI16_kralj) C++17
140 / 140
 1685 ms 61196 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
#define int ll
//500,000,000 operations
const int MAXN = 500000;
//Global Variables
int N, A[MAXN], P[MAXN], have[MAXN], st, out;
vector<int> vals[MAXN];
multiset<int> opt;
multiset<int>::iterator it;

main() {
	//ifstream cin ("test.in");
	ios_base::sync_with_stdio; cin.tie(0);
	cin >> N; ffi cin >> A[i]; ffi cin >> P[i];
	ffi {int a; cin >> a; vals[A[i]-1].pb(a);}
	int curr = 0;
	ffi {
        curr += vals[i].size(); have[i] = curr;
        curr = max(curr-1, (ll)0);
        //w<< i c have[i]<<e;
	}
	ffi if (have[i] == 0) st = (i+1)%N;
	//w<< st+1<<e;
	for (int i=st, j=0; i != st || j == 0; i=(i+1)%N, j = 1) {
        //w<< "i:" s i<<e;
        for (int k: vals[i]) opt.insert(k);
        assert(!opt.empty());
        it = opt.lower_bound(P[i]);
        if (it == opt.end()) it = opt.begin();
        else out++;
        //w<< (*it)<<e;
        opt.erase(it);
	}
	w<< out<<e;
}

Compilation message

kralj.cpp:25:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
kralj.cpp: In function 'int main()':
kralj.cpp:27:27: warning: statement is a reference, not call, to function 'std::ios_base::sync_with_stdio' [-Waddress]
  ios_base::sync_with_stdio; cin.tie(0);
                           ^
kralj.cpp:27:27: warning: statement has no effect [-Wunused-value]

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1685 ms 52052 KB Output is correct
2 Correct 1350 ms 50724 KB Output is correct
3 Correct 1461 ms 60288 KB Output is correct
4 Correct 1375 ms 61196 KB Output is correct
5 Correct 975 ms 40824 KB Output is correct
6 Correct 891 ms 40388 KB Output is correct
7 Correct 987 ms 43640 KB Output is correct
8 Correct 864 ms 40696 KB Output is correct
9 Correct 1145 ms 45432 KB Output is correct
10 Correct 1076 ms 42852 KB Output is correct